数据结构（五）图---最小生成树（克鲁斯卡尔算法）
一：回顾普里姆算法
普里姆算法是以某个顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树。是临时决定路径。
例如：我们参观某个展会，从一个入口进入，然后我们会选择最感兴趣的场馆进入观看，看完后再用同样的方法看下一个。
二：克鲁斯卡尔算法（稀疏图）
推文：https://www.cnblogs.com/qianbixin/p/5005161.html（转载自）
例如上面参观，我们为何不先决定去看那些展馆，事先计划好，然后进园后直接按照所决定的路径进行观看。这就是克鲁斯卡尔算法的思想
注意：
克鲁斯卡尔算法需要我们了解生成树的概念，我们可以回到普里姆算法回顾下
（一）基本思想
（1）构造一个只含n个顶点，边集为空的子图。若将图中各个顶点看成一棵树的根节点，则它是一个含有n棵树的森林。 （2）从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图。也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之 （3）依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。
或者
（1）将图中的所有边都去掉。
（2）将边按权值从小到大的顺序添加到图中，保证添加的过程中不会形成环
（3）重复上一步直到连接所有顶点，此时就生成了最小生成树。这是一种贪心策略。
（二）难点
判断某条边<u, v>的加入是否会在已经选定的边集集合中形成环。
（三）解决思路
使用并查集，分别找出两个顶点u, v所在树的根节点。若根节点相同，说明u, v在同一棵树中，则u, v连接起来会形成环；若根节点不同，则u, v不在一棵树中，连接起来不会形成环，而是将两棵树合并。
推文：数据结构（四）树—集合的表示及查找（并查集）
（四）图解过程
三：代码实现
数据结构定义
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> #define MAXVEX 100 //最大顶点数 #define INFINITY 65535 //用0表示∞ typedef char VertexType; //顶点类型，字符型A,B,C,D... typedef int EdgeType; //边上权值类型10,15,... //邻接矩阵结构 typedef struct { VertexType vers[MAXVEX]; //顶点表 EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵，可看作边表 int numVertexes, numEdges; //图中当前的顶点数和边数 }MGraph; typedef struct { int begin; int end; int weight; }Edge;
函数定义
//创建邻接矩阵 void CreateMGraph(MGraph* G); //邻接矩阵转边集数组 void MGraph2EdgeArr(MGraph G, Edge* edge); //显示邻接矩阵 void showGraph(MGraph G); //找到顶点index的根节点下标返回 int Find(int* parent, int index); //使用克鲁斯卡尔算法进行最小生成树的创建 void MiniSpanTree_Kruskal(MGraph G);
创建邻接矩阵
void CreateMGraph(MGraph* G) { int i, j, k, w; G->numVertexes = 9; G->numEdges = 15; //读入顶点信息 G->vers[0] = \'A\'; G->vers[1] = \'B\'; G->vers[2] = \'C\'; G->vers[3] = \'D\'; G->vers[4] = \'E\'; G->vers[5] = \'F\'; G->vers[6] = \'G\'; G->vers[7] = \'H\'; G->vers[8] = \'I\'; //getchar(); //可以获取回车符 for (i = 0; i < G->numVertexes; i++) for (j = 0; j < G->numVertexes; j++) G->arc[i][j] = INFINITY; //邻接矩阵初始化 G->arc[0][1] = 10; G->arc[0][5] = 11; G->arc[1][2] = 18; G->arc[1][6] = 16; G->arc[1][8] = 12; G->arc[2][3] = 22; G->arc[2][8] = 8; G->arc[3][4] = 20; G->arc[3][7] = 16; G->arc[3][6] = 24; G->arc[3][8] = 21; G->arc[4][5] = 26; G->arc[4][7] = 7; G->arc[5][6] = 17; G->arc[6][7] = 19; for (k = 0; k < G->numVertexes; k++) //读入numEdges条边，建立邻接矩阵 { for (i = k; i < G->numVertexes; i++) { G->arc[i][k] = G->arc[k][i]; //因为是无向图，所有是对称矩阵 } } }
CreateMGraph创建邻接矩阵
邻接矩阵转边集数组
//邻接矩阵转编辑数组，按照权值排序，由小到大 void MGraph2EdgeArr(MGraph G, Edge* edge) { int i, j,k=0; Edge temp; int min; for (i = 0; i < G.numVertexes;i++) { for (j = i + 1; j < G.numVertexes;j++) { if (G.arc[i][j]!=INFINITY) //有边 { edge[k].begin = i; edge[k].end = j; edge[k].weight = G.arc[i][j]; k++; } } } //按照冒泡大小进行排序 for (i = 0; i < k;i++) { for (j = i; j < k;j++) { if (edge[j].weight<edge[i].weight) { temp = edge[i]; edge[i] = edge[j]; edge[j] = temp; } } } }
并查集操作，获取一个顶点f的根节点下标，这里没有使用结构体，而是将数组下标作为了数据，节省了不必要空间
int Find(int* parent, int f) { while (parent[f] > 0) f = parent[f]; return f; }
使用克鲁斯卡尔算法进行最小生成树的创建
void MiniSpanTree_Kruskal(MGraph G) { Edge edges[MAXVEX]; //定义边集数组 int parent[MAXVEX]; //定义生成树的父节点，也可以使用结构体，但是更加浪费空间 int i,n,m; MGraph2EdgeArr(G, edges); //邻接矩阵转边集数组 //开始进行初始化 for (i = 0; i < MAXVEX; i++) parent[i] = 0; //这里是0代表根节点，我们也可以使用-1，正负无穷等 //进行合并操作 for (i = 0; i < G.numEdges;i++) { n = Find(parent, edges[i].begin); //找到顶点edges[i].begin的根节点下标 m = Find(parent, edges[i].end); //找到顶点edges[i].end的根节点位置 if (n!=m) //若是根节点下标不是一样的，就说不在一棵树上，不会形成环，我们放心合并 { parent[n] = m; //将n树合并到m树，表示该边被放入生成树 printf("(%d,%d) %d ", edges[i].begin, edges[i].end, edges[i].weight); } } }
全部代码
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> #define MAXVEX 100 //最大顶点数 #define INFINITY 65535 //用0表示∞ typedef char VertexType; //顶点类型，字符型A,B,C,D... typedef int EdgeType; //边上权值类型10,15,... //邻接矩阵结构 typedef struct { VertexType vers[MAXVEX]; //顶点表 EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵，可看作边表 int numVertexes, numEdges; //图中当前的顶点数和边数 }MGraph; typedef struct { int begin; int end; int weight; }Edge; //创建邻接矩阵 void CreateMGraph(MGraph* G); //邻接矩阵转边集数组 void MGraph2EdgeArr(MGraph G, Edge* edge); //显示邻接矩阵 void showGraph(MGraph G); //找到顶点index的根节点下标返回 int Find(int* parent, int index); //使用克鲁斯卡尔算法进行最小生成树的创建 void MiniSpanTree_Kruskal(MGraph G); int main() { MGraph MG; CreateMGraph(&MG); showGraph(MG); MiniSpanTree_Kruskal(MG); system("pause"); return 0; } //生成邻接矩阵 void CreateMGraph(MGraph* G) { int i, j, k, w; G->numVertexes = 9; G->numEdges = 15; //读入顶点信息 G->vers[0] = \'A\'; G->vers[1] = \'B\'; G->vers[2] = \'C\'; G->vers[3] = \'D\'; G->vers[4] = \'E\'; G->vers[5] = \'F\'; G->vers[6] = \'G\'; G->vers[7] = \'H\'; G->vers[8] = \'I\'; //getchar(); //可以获取回车符 for (i = 0; i < G->numVertexes; i++) for (j = 0; j < G->numVertexes; j++) G->arc[i][j] = INFINITY; //邻接矩阵初始化 G->arc[0][1] = 10; G->arc[0][5] = 11; G->arc[1][2] = 18; G->arc[1][6] = 16; G->arc[1][8] = 12; G->arc[2][3] = 22; G->arc[2][8] = 8; G->arc[3][4] = 20; G->arc[3][7] = 16; G->arc[3][6] = 24; G->arc[3][8] = 21; G->arc[4][5] = 26; G->arc[4][7] = 7; G->arc[5][6] = 17; G->arc[6][7] = 19; for (k = 0; k < G->numVertexes; k++) //读入numEdges条边，建立邻接矩阵 { for (i = k; i < G->numVertexes; i++) { G->arc[i][k] = G->arc[k][i]; //因为是无向图，所有是对称矩阵 } } } //邻接矩阵转编辑数组，按照权值排序，由小到大 void MGraph2EdgeArr(MGraph G, Edge* edge) { int i, j,k=0; Edge temp; int min; for (i = 0; i < G.numVertexes;i++) { for (j = i + 1; j < G.numVertexes;j++) { if (G.arc[i][j]!=INFINITY) //有边 { edge[k].begin = i; edge[k].end = j; edge[k].weight = G.arc[i][j]; k++; } } } //按照冒泡大小进行排序 for (i = 0; i < k;i++) { for (j = i; j < k;j++) { if (edge[j].weight<edge[i].weight) { temp = edge[i]; edge[i] = edge[j]; edge[j] = temp; } } } } //显示邻接矩阵 void showGraph(MGraph G) { for (int i = 0; i < G.numVertexes; i++) { for (int j = 0; j < G.numVertexes; j++) { if (G.arc[i][j] != INFINITY) printf("%5d", G.arc[i][j]); else printf(" 0"); } printf("\n"); } } //并查集操作，获取一个顶点f的根节点下标 int Find(int* parent, int f) { while (parent[f] > 0) f = parent[f]; return f; } //使用克鲁斯卡尔算法进行最小生成树的创建 void MiniSpanTree_Kruskal(MGraph G) { Edge edges[MAXVEX]; //定义边集数组 int parent[MAXVEX]; //定义生成树的父节点，也可以使用结构体，但是更加浪费空间 int i, n, m; MGraph2EdgeArr(G, edges); //邻接矩阵转边集数组 //开始进行初始化 for (i = 0; i < MAXVEX; i++) parent[i] = 0; //这里是0代表根节点，我们也可以使用-1，正负无穷等 //进行合并操作 for (i = 0; i < G.numEdges; i++) { n = Find(parent, edges[i].begin); //找到顶点edges[i].begin的根节点下标 m = Find(parent, edges[i].end); //找到顶点edges[i].end的根节点位置 if (n != m) //若是根节点下标不是一样的，就说不在一棵树上，不会形成环，我们放心合并 { parent[n] = m; //将n树合并到m树，表示该边被放入生成树 printf("(%d,%d) %d ", edges[i].begin, edges[i].end, edges[i].weight); } } }
View Code
四：总结
将图中各边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边, 若形成回路则除去.依次选够(n-1)条边,即得最小生成树.(n为顶点数)
克鲁斯卡尔算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。（若图的顶点数为n，边数为e）。
版权声明：本文为ssyfj原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。