Kruskal算法的基本过程：任给一个有n个顶点的连通网络N={V,E}，首先构造一个由这n个顶点组成、不含任何边的图T={V,},其中每个顶点自成一个连通分量。不断从E中取出权值最小的一条边（若有多条，任取其一），若该边的两个端点来自不同的连通分量，则将此边加入到T中。如此重复，直到所有顶点在同一个连通分量上为止。
实现分析：
由于需要不断判断两个端点是否来自同一个连通分量，否的话，两个连通分量的顶点并起来，这里可以用并查集实现。由于不断从边集中取出权值最小的一条边，这里可以用最小堆来实现。下面提供面向邻接矩阵和面向邻接表的Kruskal算法实现：
// // main.cpp // Kruskal-最小生成树 // // Created by scnulpc on 2018/10/25. // Copyright © 2018年 scnulpc. All rights reserved. // #include <iostream> #include <queue> #define maxWeight 99 #define size 100 using namespace std; //邻接矩阵的存储结构 struct Edge { int v1,v2; int weight; Edge(int a,int b,int cost):v1(a),v2(b),weight(cost){} friend bool operator < (Edge a,Edge b) { return a.weight > b.weight; //权重小的优先级高，构造最小堆 } }; int map[size][size]; //邻接表的存储结构 struct edge { int dest; int weight; edge* link; edge(int a,int b):dest(a),weight(b),link(NULL){} }; struct VertexNode { int v; edge* adjacent; VertexNode(int a):v(a),adjacent(NULL){} }; VertexNode* vertecies[size]; int Find(int x,int *parent) { if (parent[x]<0) return x; else return Find(parent[x], parent); } bool Union(int v1,int v2,int *parent) { int num1 = Find(v1, parent); int num2 = Find(v2, parent); if (num1==num2&&num1!=-1) return false; if (num1<num2) { parent[num1] += parent[num2]; parent[num2] = num1; } else { parent[num2]+=parent[num1]; parent[num1] = num2; } return true; } //基于邻接矩阵的有权无向图的Kruskal算法 void Kruskal(int n) { priority_queue<Edge> q; int UFSet[n]; for (int i=0; i<n; i++) {UFSet[i]=-1;} for (int i=0; i<n; i++) { for (int j=i+1; j<n; j++) { if (map[i][j]>0&&map[i][j]<maxWeight) { q.push(*(new Edge(i,j,map[i][j]))); } } } //上面都是准备工作，初始化并查集，所有边入最小堆 int vertex = 1; while (vertex!=n&&!q.empty()) { Edge top = q.top();q.pop(); if(Union(top.v1, top.v2, UFSet)) vertex++; } if (vertex==n) cout<<"最小生成树已生成"<<endl; //这个判断条件也可以为 是否存在这样的n-1条边，把n个顶点连接起来 else cout<<"不存在最小生成树"<<endl; } //基于邻接表有权无向图(有向图)的Kruskal算法 void Kruskal1(int n) { priority_queue<Edge> q; int UFSet[n]; for (int i=0; i<n; i++) UFSet[i]=-1; for (int i=0; i<n; i++) { edge* p = vertecies[i]->adjacent; while (p!=NULL) { q.push(*(new Edge(i,p->dest,p->weight))); //如果为无向图，这里可以改进，判断边的重复，进一半的边 p=p->link; } } int numEdge = 0; int count = 1; while (count!=n&&!q.empty()) { Edge temp = q.top();q.pop(); if (Union(temp.v1, temp.v2, UFSet)) { numEdge++; } } if (numEdge==n-1) { cout<<"最小生成树存在"<<endl; } else { cout<<"最小生成树不存在"<<endl; } } /* 测试数据 0 1 99 3 99 1 0 2 4 99 99 2 0 99 99 3 99 99 0 5 99 99 99 5 0 */ int main(int argc, const char * argv[]) { int n=5; for (int i=0; i<n; i++) { for (int j=0; j<n; j++) { cin>>map[i][j]; } } Kruskal(n); for (int i=0; i<n; i++) { vertecies[i] = new VertexNode(i); } vertecies[0]->adjacent = new edge(1,1); vertecies[0]->adjacent->link = new edge(3,3); vertecies[1]->adjacent = new edge(0,1); vertecies[1]->adjacent->link = new edge(2,2); vertecies[1]->adjacent->link->link = new edge(3,4); vertecies[2]->adjacent = new edge(1,2); vertecies[3]->adjacent = new edge(0,3); vertecies[3]->adjacent->link = new edge(4,5); vertecies[4]->adjacent = new edge(3,5); Kruskal1(n); return 0; }
