生成树
连通图的生成树：是该图的 极小连通子图，即：含有图中全部 n 个顶点，但只有 n-1 条边
如下图：
分类
图的生成树 不是唯一 的。从不同的顶点出发，选择不同的存储方式，用不同的求解方法,可以得到不同的生成树。
- 由深度优先搜索遍历得到的生成树，称为 深度优先 生成树
- 由广度优先搜索遍历得到的生成树，称为 广度优先 生成树
下图中无向图G7的两种生成树：
最小生成树
图的所有生成树中，边上的 权值之和最小 的树
构造最小生成树的3个准则
- 只能使用该网络的边来构造最小生成树
- 只能使用
n-1条边来连接n个顶点 - 不能形成环路
算法
- 普里姆（Prim）算法
- 克鲁斯卡尔(Kruskal)算法
克鲁斯卡尔(Kruskal)算法
每次选取图中 权值最小的边，直到把所有点连起来
注意：不能形成环路
时间复杂度
时间复杂度为 O(e\log_2e) （e 边的数量）
计算过程：为了实现 “每次选取图中 权值最小的边”，所以要先从小到大排序，而排序算法最快就是 O(e\log_2e)，主要耗时就是排序
特点
与图中的 顶点数量无关，适合于求 边稀疏 的网的最小生成树。
普里姆（Prim）算法
从 某个点开始，找该点 权值最小 的边，直到把所有点连起来
注意：不能形成环路
时间复杂度
用 邻接矩阵 存储，时间复杂度为 O(n²) （n 顶点数量）
计算过程：
- 每次要找离生成树最近的点
- 都要把所有 V 个顶点扫一遍
一共找 V 次，所以：O(V × V) = O(V²)
特点
与图中的 边数无关，因此该算法适合于求 边稠密的网 的最小生成树。
Kruskal和Prim的对比
| Kruskal 算法 | Prim 算法 | |
|---|---|---|
| 算法类型 | 贪心算法 | 贪心算法 |
| 适用图类型 | 稀疏图，特别适合边权值分布较广的图 | 稠密图，特别适合顶点多边多的图 |
| 基本思想 | 从边的角度出发，按权值从小到大选择边 | 从顶点出发，每次扩展最小权值的边 |
| 时间复杂度 | O(nlog₂n) | O(n²) |
| 典型应用 | 网络设计问题，边多且分散的图 | 电网、网络设计问题，稠密的图 |
| 贪心选择标准 | 每次选择权值最小且不形成环的边 | 每次选择最小的连接权值，扩展已加入的顶点集合 |
- Kruskal：适用于 稀疏图，因为其从边的角度出发，边的数量相对少时效率更高。
- Prim：适用于 稠密图，因为它每次从顶点出发，逐渐扩展树，对于稠密图（边多的图）效率更高
参考：
https://blog.csdn.net/Peisenli/article/details/100114809
https://blog.csdn.net/2301_79188764/article/details/142172901