kurskal算法更适合稀疏图
kruskal算法伪代码:
1 int kruskal(){ 2 令最小生成树的边权之和为ans, 最小生成树的当前边数为Num_Edge; 3 将所有边按边权从小到大排序; 4 for (从小到大枚举所有的边){ 5 if (当前测试边的两个端点在不同的连通块中){ 6 将测试边加入最小生成树中; 7 ans += 测试边的边权; 8 最小生成树的当前边数Num_Edge加一; 9 当前边数Num_Edge等于顶点数减1是结束循环; 10 } 11 12 } 13 return ans; 14 }
具体实现:
1 struct edge{ 2 int u, v; //边的两个端点编号 3 int cost; //边权 4 }E[MAXV]; 5 6 bool cmp(edge a, edge b){ 7 return a.cost < b.cost; 8 } 9 int father[MAXV]; //并查集数组 10 11 //并查集查询函数 12 int findFather(int x){ 13 int a = x; 14 while (x != father[x]){ 15 x = father[x]; 16 } 17 18 //路径压缩 19 while (a != father[a]){ 20 int z = a; 21 a = father[a]; 22 father[z] = x; 23 } 24 25 return x; 26 } 27 28 //kruskal函数返回最小生成树的边权之和,参数n为顶点个数, m为图的边数 29 int kruskal(int n, int m){ 30 int ans = 0, Num_Edge = 0; //最小边权之和,当前生成树的边数 31 //初始化并查集 32 for (int i = 1; i <= n; i++){ 33 father[i] = i; 34 } 35 36 //对所有边排序 37 sort(E, E + m, cmp); 38 //遍历所有的边 39 for (int i = 0; i < m; i++){ 40 int faU = findFather(E[i].u); //查询测试边两个端点所在集合的根节点 41 int faV = findFather(E[i].v); 42 if (faU != faV){ 43 father[faV] = faU; 44 ans += E[i].cost; 45 Num_Edge++; 46 if (Num_Edge == n - 1) break; //如果已经建成了一棵树,跳出循环 47 } 48 } 49 if (Num_Edge != n - 1) return -1; //当图不连通时,返回-1 50 else return ans; //否则返回最小生成树的边权之和 51 }