DSA - 生成树(Spanning Tree)
生成树是图G的子集，其具有覆盖有最小可能边数的所有顶点。 因此，生成树没有循环，也无法断开连接。
通过这个定义，我们可以得出结论，每个连通和无向图G都至少有一个生成树。 断开连接的图形没有任何生成树，因为它不能跨越所有顶点。
我们从一个完整的图表中找到了三棵生成树。 完整的无向图可以具有最大n n-2个生成树数，其中n是节点数。 在上面提到的示例中， n is 3,因此3 3−2 = 3生成树是可能的。
生成树的一般属性
我们现在知道一个图可以有多个生成树。 以下是连接到图G的生成树的一些属性 -
连接图G可以具有多个生成树。
图G的所有可能的生成树具有相同数量的边和顶点。
生成树没有任何循环（循环）。
从生成树中删除一条边将使图形断开连接，即生成树minimally connected 。
向生成树添加一条边将创建一个电路或循环，即生成树maximally acyclic 。
生成树的数学性质
生成树有n-1边，其中n是节点数（顶点）。
从完整的图表中，通过删除最大e - n + 1边，我们可以构建生成树。
完整的图形可以具有最多n n-2个生成树。
因此，我们可以得出结论，生成树是连接图G的子集，而断开连接的图没有生成树。
生成树的应用
生成树主要用于查找连接图中所有节点的最小路径。 生成树的常见应用是 -
Civil Network Planning
Computer Network Routing Protocol
Cluster Analysis
让我们通过一个小例子来理解这一点。 考虑一下，城市网络是一个巨大的图形，现在计划以这样的方式部署电话线，即在最小线路中我们可以连接到所有城市节点。 这是生成树进入图片的地方。
Minimum Spanning Tree (MST)
在加权图中，最小生成树是生成树，其权重最小于同一图的所有其他生成树。 在实际情况中，该权重可以被测量为距离，拥塞，交通负载或任何表示边缘的任意值。
最小生成树算法
我们将在这里学习两个最重要的生成树算法 -
两者都是贪婪的算法。
