C语言数据结构系列最小生成树篇C语言数据结构系列十五最小生成树——Prim与Kruskal一、前言二、基本概念2.1 什么是生成树2.2 什么是最小生成树三、Prim算法3.1 思想3.2 步骤3.3 代码实现四、Kruskal算法4.1 思想4.2 步骤4.3 代码实现五、Prim vs Kruskal六、应用七、下篇预告C语言数据结构系列十五最小生成树——Prim与Kruskal本篇目标理解最小生成树概念掌握Prim和Kruskal算法摘要本文讲解最小生成树MST的核心概念并深入对比两种经典算法——Prim 与 Kruskal。Prim 从点出发适合稠密图Kruskal 从边出发借助并查集检测环适合稀疏图。文中配有图解、步骤流程与完整 C 语言代码实现帮助读者快速掌握两种算法的思想、步骤与适用场景。一、前言哈喽小伙伴们今天我们来学习最小生成树MST——用最少的边连接所有顶点应用场景 电网设计️ 公路规划 网络布线二、基本概念2.1 什么是生成树生成树包含图中所有顶点的无环连通子图2.2 什么是最小生成树最小生成树边权值之和最小的生成树42351ABCDMSTA-C(2), C-D(1), B-C(3) 总权值6三、Prim算法3.1 思想从点出发从一个顶点开始每次加入权值最小的边3.2 步骤1. 从A开始2. 加入最小边A-C3. 加入最小边C-D4. 加入最小边B-C3.3 代码实现#defineINF99999voidprim(intgraph[][MAX],intn){intkey[MAX];// 到生成树的最小距离bool inMST[MAX];// 是否在MST中intparent[MAX];// 父节点for(inti0;in;i){key[i]INF;inMST[i]false;parent[i]-1;}key[0]0;// 从顶点0开始for(intcount0;countn-1;count){// 找key最小且不在MST中的顶点intu-1;for(intv0;vn;v){if(!inMST[v](u-1||key[v]key[u])){uv;}}inMST[u]true;// 更新邻接顶点的keyfor(intv0;vn;v){if(graph[u][v]!inMST[v]graph[u][v]key[v]){key[v]graph[u][v];parent[v]u;}}}printf(Prim MST:\n);for(inti1;in;i){printf(%c - %c : %d\n,parent[i]A,iA,key[i]);}}四、Kruskal算法4.1 思想从边出发按权值排序依次加入不形成环的边使用并查集检测环4.2 步骤1. 所有边排序2. 选最小边C-D3. 选次小边A-C4. 选B-C形成环则跳过4.3 代码实现typedefstruct{intu,v,weight;}Edge;intparent[MAX];intrank[MAX];voidinitUnionFind(intn){for(inti0;in;i){parent[i]i;rank[i]0;}}intfind(intx){if(parent[x]!x){parent[x]find(parent[x]);}returnparent[x];}boolunion(intx,inty){intpxfind(x),pyfind(y);if(pxpy)returnfalse;if(rank[px]rank[py])parent[px]py;elseif(rank[px]rank[py])parent[py]px;else{parent[py]px;rank[px];}returntrue;}intcmp(constvoid*a,constvoid*b){return((Edge*)a)-weight-((Edge*)b)-weight;}voidkruskal(Edge edges[],intedgeNum,intn){qsort(edges,edgeNum,sizeof(Edge),cmp);initUnionFind(n);printf(Kruskal MST:\n);intcount0;for(inti0;iedgeNumcountn-1;i){if(union(edges[i].u,edges[i].v)){printf(%c - %c : %d\n,edges[i].uA,edges[i].vA,edges[i].weight);count;}}}五、Prim vs Kruskal特性PrimKruskal思想从点出发从边出发时间O(V²)O(ElogE)适用稠密图稀疏图数据结构数组并查集六、应用电网设计⚡最低成本连接所有城市网络布线最少网线连接所有电脑聚类分析去掉最大边实现K类聚类七、下篇预告下一篇我们将学习最短路径Dijkstra与Floyd Prim适合稠密图Kruskal适合稀疏图 15-最小生成树：Prim与Kruskal
C语言数据结构系列最小生成树篇C语言数据结构系列十五最小生成树——Prim与Kruskal一、前言二、基本概念2.1 什么是生成树2.2 什么是最小生成树三、Prim算法3.1 思想3.2 步骤3.3 代码实现四、Kruskal算法4.1 思想4.2 步骤4.3 代码实现五、Prim vs Kruskal六、应用七、下篇预告C语言数据结构系列十五最小生成树——Prim与Kruskal本篇目标理解最小生成树概念掌握Prim和Kruskal算法摘要本文讲解最小生成树MST的核心概念并深入对比两种经典算法——Prim 与 Kruskal。Prim 从点出发适合稠密图Kruskal 从边出发借助并查集检测环适合稀疏图。文中配有图解、步骤流程与完整 C 语言代码实现帮助读者快速掌握两种算法的思想、步骤与适用场景。一、前言哈喽小伙伴们今天我们来学习最小生成树MST——用最少的边连接所有顶点应用场景 电网设计️ 公路规划 网络布线二、基本概念2.1 什么是生成树生成树包含图中所有顶点的无环连通子图2.2 什么是最小生成树最小生成树边权值之和最小的生成树42351ABCDMSTA-C(2), C-D(1), B-C(3) 总权值6三、Prim算法3.1 思想从点出发从一个顶点开始每次加入权值最小的边3.2 步骤1. 从A开始2. 加入最小边A-C3. 加入最小边C-D4. 加入最小边B-C3.3 代码实现#defineINF99999voidprim(intgraph[][MAX],intn){intkey[MAX];// 到生成树的最小距离bool inMST[MAX];// 是否在MST中intparent[MAX];// 父节点for(inti0;in;i){key[i]INF;inMST[i]false;parent[i]-1;}key[0]0;// 从顶点0开始for(intcount0;countn-1;count){// 找key最小且不在MST中的顶点intu-1;for(intv0;vn;v){if(!inMST[v](u-1||key[v]key[u])){uv;}}inMST[u]true;// 更新邻接顶点的keyfor(intv0;vn;v){if(graph[u][v]!inMST[v]graph[u][v]key[v]){key[v]graph[u][v];parent[v]u;}}}printf(Prim MST:\n);for(inti1;in;i){printf(%c - %c : %d\n,parent[i]A,iA,key[i]);}}四、Kruskal算法4.1 思想从边出发按权值排序依次加入不形成环的边使用并查集检测环4.2 步骤1. 所有边排序2. 选最小边C-D3. 选次小边A-C4. 选B-C形成环则跳过4.3 代码实现typedefstruct{intu,v,weight;}Edge;intparent[MAX];intrank[MAX];voidinitUnionFind(intn){for(inti0;in;i){parent[i]i;rank[i]0;}}intfind(intx){if(parent[x]!x){parent[x]find(parent[x]);}returnparent[x];}boolunion(intx,inty){intpxfind(x),pyfind(y);if(pxpy)returnfalse;if(rank[px]rank[py])parent[px]py;elseif(rank[px]rank[py])parent[py]px;else{parent[py]px;rank[px];}returntrue;}intcmp(constvoid*a,constvoid*b){return((Edge*)a)-weight-((Edge*)b)-weight;}voidkruskal(Edge edges[],intedgeNum,intn){qsort(edges,edgeNum,sizeof(Edge),cmp);initUnionFind(n);printf(Kruskal MST:\n);intcount0;for(inti0;iedgeNumcountn-1;i){if(union(edges[i].u,edges[i].v)){printf(%c - %c : %d\n,edges[i].uA,edges[i].vA,edges[i].weight);count;}}}五、Prim vs Kruskal特性PrimKruskal思想从点出发从边出发时间O(V²)O(ElogE)适用稠密图稀疏图数据结构数组并查集六、应用电网设计⚡最低成本连接所有城市网络布线最少网线连接所有电脑聚类分析去掉最大边实现K类聚类七、下篇预告下一篇我们将学习最短路径Dijkstra与Floyd Prim适合稠密图Kruskal适合稀疏图 RELATED READING
延伸阅读
更多一线实战笔记与深度复盘，助您持续精进
