软考-软件设计师：数据结构-图：生成树、最小生成树、克鲁斯卡尔(Kruskal)算法、普里姆（Prim）算法 作者：马育民 • 2025-04-13 16:55 • 阅读：10010 # 生成树 连通图的生成树：是该图的 **极小连通子图**，即：含有图中全部 `n` 个顶点，但只有 `n-1` 条边 如下图： [](https://www.malaoshi.top/upload/0/0/1GWwE7zsDCO.png) ### 分类 图的生成树 **不是唯一** 的。从不同的顶点出发，选择不同的存储方式，用不同的求解方法,可以得到不同的生成树。 - 由深度优先搜索遍历得到的生成树，称为 **深度优先** 生成树 - 由广度优先搜索遍历得到的生成树，称为 **广度优先** 生成树 下图中无向图G7的两种生成树： [](https://www.malaoshi.top/upload/0/0/1GWwECnOC4Z.png) # 最小生成树 图的所有生成树中，边上的 **权值之和最小** 的树 ### 构造最小生成树的3个准则 - 只能使用该网络的边来构造最小生成树 - 只能使用 `n-1` 条边来连接 `n` 个顶点 - **不能形成环路** ### 算法 - 普里姆（Prim）算法 - 克鲁斯卡尔(Kruskal)算法 ### 克鲁斯卡尔(Kruskal)算法 每次选取图中 **权值最小的边**，直到把所有点连起来 **注意：**不能形成环路 [](https://www.malaoshi.top/upload/0/0/1GWwEavkY3Z.png) #### 时间复杂度 时间复杂度为 `O(eloge)` （`e` 边的数量） **特点：**与图中的 **顶点数量无关**，适合于求 **边稀疏** 的网的最小生成树。 ### 普里姆（Prim）算法 从 **某个点开始**，找该点 **权值最小** 的边，直到把所有点连起来 **注意：**不能形成环路 [](https://www.malaoshi.top/upload/0/0/1GWwEU1qkqC.png) #### 时间复杂度 时间复杂度为 `O(n²)` （`n` 顶点数量） **特点：**与图中的 **边数无关**，因此该算法适合于求 **边稠密的网** 的最小生成树。 # 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 原文出处：http://malaoshi.top/show_1GWwGMkdgg9.html