目录一、最小生成树基础概念1.1 什么是最小生成树1.2 应用场景二、Prim算法2.1 算法思想2.2 图解示例2.3 代码实现三、Kruskal算法3.1 算法思想3.2 并查集实现3.3 边结构体3.4 Kruskal算法实现四、Prim vs Kruskal五、完整性能对比六、算法选择建议七、小结八、思考题一、最小生成树基础概念1.1 什么是最小生成树对于一个带权无向连通图生成树是包含所有顶点的无环连通子图。最小生成树是边权之和最小的生成树。示例text原图 最小生成树 1 —— 2 1 —— 2 | \ | \ | 4 5 3 5 3 | \| \ | 4 —— 5 4 边权和1345131.2 应用场景场景说明网络布线铺设成本最低的线路道路建设连接所有城市的最短公路电路设计连接所有引脚的最短连线聚类分析最小生成树切割用于分类二、Prim算法2.1 算法思想Prim算法是贪心算法从一个顶点开始每次选择连接已选集合和未选集合的最短边将新顶点加入集合直到所有顶点都被覆盖。步骤任选一个起点加入集合U在连接U和V-U的边中选权值最小的边将对应顶点加入U重复步骤2直到U包含所有顶点2.2 图解示例text初始图 1 0 — 1 | / \ 4 2 3 | / \ 2 — 3 — 4 5 6 起点0 U{0}选边0-1(1) U{0,1}选边1-2(2) U{0,1,2}选边2-3(5) U{0,1,2,3}选边3-4(6) U{0,1,2,3,4}2.3 代码实现c#include stdio.h #include stdlib.h #include limits.h #define MAX_VERTICES 100 #define INF INT_MAX // Prim算法邻接矩阵 void prim(int graph[MAX_VERTICES][MAX_VERTICES], int n) { int selected[MAX_VERTICES] {0}; // 是否已在生成树中 int minEdge[MAX_VERTICES]; // 到当前树的最小边权 int parent[MAX_VERTICES]; // 记录父节点 // 初始化 for (int i 0; i n; i) { minEdge[i] INF; parent[i] -1; } // 从顶点0开始 minEdge[0] 0; int totalWeight 0; for (int count 0; count n; count) { // 找到未选顶点中minEdge最小的顶点 int u -1; for (int i 0; i n; i) { if (!selected[i] (u -1 || minEdge[i] minEdge[u])) { u i; } } selected[u] 1; totalWeight minEdge[u]; // 输出选中的边 if (parent[u] ! -1) { printf(边 %d - %d 权值: %d\n, parent[u], u, minEdge[u]); } // 更新相邻顶点的minEdge for (int v 0; v n; v) { if (graph[u][v] ! INF !selected[v] graph[u][v] minEdge[v]) { minEdge[v] graph[u][v]; parent[v] u; } } } printf(最小生成树总权值: %d\n, totalWeight); } int main() { int n 5; int graph[MAX_VERTICES][MAX_VERTICES]; // 初始化无穷大 for (int i 0; i n; i) { for (int j 0; j n; j) { graph[i][j] (i j) ? 0 : INF; } } // 添加边 graph[0][1] graph[1][0] 1; graph[0][2] graph[2][0] 4; graph[1][2] graph[2][1] 2; graph[1][3] graph[3][1] 3; graph[2][3] graph[3][2] 5; graph[2][4] graph[4][2] 4; graph[3][4] graph[4][3] 6; printf(Prim算法最小生成树:\n); prim(graph, n); return 0; }运行结果textPrim算法最小生成树: 边 0 - 1 权值: 1 边 1 - 2 权值: 2 边 1 - 3 权值: 3 边 2 - 4 权值: 4 最小生成树总权值: 10三、Kruskal算法3.1 算法思想Kruskal算法也是贪心算法按边权从小到大考虑如果加入该边不会形成环就加入生成树。需要并查集来检测是否形成环。步骤将所有边按权值从小到大排序初始化并查集每个顶点独立遍历每条边如果边的两个顶点不在同一集合加入生成树合并集合重复直到生成树有 n-1 条边3.2 并查集实现c// 并查集结构 typedef struct { int parent[MAX_VERTICES]; int rank[MAX_VERTICES]; } UnionFind; // 初始化 void ufInit(UnionFind *uf, int n) { for (int i 0; i n; i) { uf-parent[i] i; uf-rank[i] 0; } } // 查找路径压缩 int ufFind(UnionFind *uf, int x) { if (uf-parent[x] ! x) { uf-parent[x] ufFind(uf, uf-parent[x]); } return uf-parent[x]; } // 合并按秩合并 void ufUnion(UnionFind *uf, int x, int y) { int rootX ufFind(uf, x); int rootY ufFind(uf, y); if (rootX rootY) return; if (uf-rank[rootX] uf-rank[rootY]) { uf-parent[rootX] rootY; } else if (uf-rank[rootX] uf-rank[rootY]) { uf-parent[rootY] rootX; } else { uf-parent[rootY] rootX; uf-rank[rootX]; } }3.3 边结构体ctypedef struct { int u, v, weight; } Edge; // 比较函数用于排序 int cmpEdge(const void *a, const void *b) { return ((Edge*)a)-weight - ((Edge*)b)-weight; }3.4 Kruskal算法实现c#include stdio.h #include stdlib.h #include limits.h #define MAX_VERTICES 100 #define MAX_EDGES 1000 typedef struct { int u, v, weight; } Edge; typedef struct { int parent[MAX_VERTICES]; int rank[MAX_VERTICES]; } UnionFind; void ufInit(UnionFind *uf, int n) { for (int i 0; i n; i) { uf-parent[i] i; uf-rank[i] 0; } } int ufFind(UnionFind *uf, int x) { if (uf-parent[x] ! x) { uf-parent[x] ufFind(uf, uf-parent[x]); } return uf-parent[x]; } void ufUnion(UnionFind *uf, int x, int y) { int rootX ufFind(uf, x); int rootY ufFind(uf, y); if (rootX rootY) return; if (uf-rank[rootX] uf-rank[rootY]) { uf-parent[rootX] rootY; } else if (uf-rank[rootX] uf-rank[rootY]) { uf-parent[rootY] rootX; } else { uf-parent[rootY] rootX; uf-rank[rootX]; } } int cmpEdge(const void *a, const void *b) { return ((Edge*)a)-weight - ((Edge*)b)-weight; } void kruskal(Edge edges[], int n, int edgeCount) { // 1. 按权值排序 qsort(edges, edgeCount, sizeof(Edge), cmpEdge); // 2. 初始化并查集 UnionFind uf; ufInit(uf, n); // 3. 选择边 int selectedEdges 0; int totalWeight 0; printf(Kruskal算法最小生成树:\n); for (int i 0; i edgeCount selectedEdges n - 1; i) { int u edges[i].u; int v edges[i].v; int w edges[i].weight; if (ufFind(uf, u) ! ufFind(uf, v)) { ufUnion(uf, u, v); printf(边 %d - %d 权值: %d\n, u, v, w); totalWeight w; selectedEdges; } } printf(最小生成树总权值: %d\n, totalWeight); } int main() { Edge edges[] { {0, 1, 1}, {0, 2, 4}, {1, 2, 2}, {1, 3, 3}, {2, 3, 5}, {2, 4, 4}, {3, 4, 6} }; int edgeCount sizeof(edges) / sizeof(edges[0]); kruskal(edges, 5, edgeCount); return 0; }运行结果textKruskal算法最小生成树: 边 0 - 1 权值: 1 边 1 - 2 权值: 2 边 1 - 3 权值: 3 边 2 - 4 权值: 4 最小生成树总权值: 10四、Prim vs Kruskal对比项Prim算法Kruskal算法核心思想从顶点扩展从边选择数据结构数组/堆并查集时间复杂度O(V²)数组/ O(E log V)堆O(E log E)适用图稠密图稀疏图实现复杂度中等中等需并查集是否依赖起点是否时间复杂度分析Prim邻接矩阵O(V²)适合 V ≤ 2000Prim二叉堆邻接表O(E log V)适合稀疏图KruskalO(E log E)主要开销在排序五、完整性能对比c#include stdio.h #include stdlib.h #include time.h // 生成随机图 void generateRandomGraph(int n, int edgeCount, Edge edges[]) { srand(time(NULL)); for (int i 0; i edgeCount; i) { edges[i].u rand() % n; edges[i].v rand() % n; while (edges[i].u edges[i].v) { edges[i].v rand() % n; } edges[i].weight rand() % 100 1; } } int main() { int n 100; // 顶点数 int sparseEdges 500; // 稀疏图约 5n 条边 int denseEdges 5000; // 稠密图约 50n 条边 Edge *edges (Edge*)malloc(denseEdges * sizeof(Edge)); // 稀疏图测试 generateRandomGraph(n, sparseEdges, edges); clock_t start clock(); kruskal(edges, n, sparseEdges); clock_t end clock(); printf(Kruskal(稀疏图): %.2f ms\n\n, (double)(end - start) / CLOCKS_PER_SEC * 1000); // 稠密图测试 generateRandomGraph(n, denseEdges, edges); start clock(); kruskal(edges, n, denseEdges); end clock(); printf(Kruskal(稠密图): %.2f ms\n\n, (double)(end - start) / CLOCKS_PER_SEC * 1000); free(edges); return 0; }六、算法选择建议场景推荐理由稠密图边数接近 V²Prim邻接矩阵O(V²) 优于 O(E log E)稀疏图边数接近 VKruskalO(E log E) 很快需要处理大量顶点Kruskal内存占用小实现简单Prim数组版代码量少动态添加顶点Prim可以增量扩展七、小结这一篇我们学习了最小生成树的两种经典算法算法核心数据结构时间复杂度适用场景Prim顶点扩展数组/堆O(V²) / O(E log V)稠密图Kruskal边选择并查集O(E log E)稀疏图关键点Prim维护到当前树的最短距离Kruskal边排序 并查集判环并查集路径压缩 按秩合并下一篇我们讲最短路径Dijkstra与Floyd。八、思考题Prim算法从一个顶点开始如果从不同顶点开始得到的最小生成树相同吗Kruskal算法中为什么排序后按顺序选边就能得到最小生成树如果图中有权值相同的边最小生成树是否唯一并查集的路径压缩和按秩合并分别优化了什么欢迎在评论区讨论你的答案。