上查看所有课程
在我们学习生成树之前，我们需要理解两个图：无向图和连通图。
无向图是一种边没有指向任何方向的图（即边是双向的）。
连通图是指图中任意两个顶点之间总存在路径的图。
生成树
生成树是无向连通图的一个子图，它包含图的所有顶点，并且具有最少的边数。如果遗漏了某个顶点，则不是生成树。
边可以有权值，也可以没有。
具有 n 个顶点的生成树，可以从完全图中创建出的总数为 n(n-2)。
如果我们有 n = 4，则可能的生成树的最大数量为 44-2 = 16。因此，可以从具有 4 个顶点的完全图中形成 16 棵生成树。
生成树示例
让我们通过下面的示例来理解生成树
原始图为
从上图可以创建的生成树的一些可能选项是
最小生成树
最小生成树是指生成树中边的权值之和尽可能小的生成树。
生成树示例
让我们通过下面的例子来理解上述定义。
初始图是
从上述图中可能的生成树是
上述生成树中的最小生成树是
最小生成树通常使用以下算法找到
生成树的应用
- 计算机网络路由协议
- 聚类分析
- 市政网络规划
最小生成树的应用
- 查找地图中的路径
- 设计电信网络、供水网络和电网等网络。