生成树
什么是生成树？
生成树是图 G 的一个子集，其所有顶点都被尽可能少的边覆盖。因此，生成树没有环，也不能断开连接。
根据此定义，我们可以得出结论：每个连通且无向的图 G 至少有一个生成树。断开连接的图没有任何生成树，因为它无法生成到其所有顶点。
我们从一个完全图中找到了三棵生成树。完全无向图最多可以有 nn-2 个生成树，其中 n 是节点数。在上面的例子中，n 为 3，因此 33−2 = 3 生成树是可能的。
生成树的一般性质
现在我们知道一个图可以有多棵生成树。以下是连通图 G 的生成树的一些性质 −
连通图 G 可以有多棵生成树。
图 G 的所有可能的生成树都具有相同数量的边和顶点。
生成树没有任何循环（回路）。
从生成树中删除一条边将使图断开，即生成树是最小连通的。
向生成树添加一条边将创建一个电路或环，即生成树是最大无环的。
生成树的数学性质
生成树有 n-1 条边，其中 n 是节点（顶点）的数量。
从完全图中，通过移除最多 e - n + 1 条边，我们可以构造一棵生成树。
完全图最多可以有 nn-2 个生成树。
因此，我们可以得出结论，生成树是连通图 G 的子集，而不连通图没有生成树。
生成树的应用
生成树的基本用途是找到连接图中所有节点的最小路径。生成树的常见应用是−
民用网络规划
计算机网络路由协议
聚类分析
让我们通过一个小例子来理解这一点。假设城市网络是一个巨大的图，现在计划以最少的线路连接到所有城市节点的方式部署电话线路。这就是生成树的用武之地。
最小生成树 (MST)
在加权图中，最小生成树是指比同一图中所有其他生成树的权重都最小的生成树。在实际情况下，该权重可以用距离、拥塞度、流量负载或任何表示为边的任意值来衡量。
最小生成树算法
我们将在这里学习两种最重要的生成树算法 −
这两种算法都是贪婪算法。
