最小生成树(MinSpanTree)的Kruskal算法

分析

最小生成树的克鲁斯卡尔(Kruskal)算法实现主要是通过将输入的图的边存在优先队列中，然后依次从优先队列中取最小的边加入生成树，最小生成树的边的个数是顶点数减一，因此退出条件是while (!pq.empty() || cnt < n - 1)，其中需要注意的是在定义边结点EdgeNode时需要重载运算符<，因为在优先队列priority_queue中的实现逻辑就是需要比较元素的大小，那么在自定义结构体中则需要重载该运算符。 另外一个知识点就是并查集，这个数据结构的实现方式比较简单，类似于树的实现方式，具体知识可参考资料。总的来说，Kruskal算法的实现还是相对简单的。

C/C++代码实现

/******************************************************* * Kruskal算法实现最小生成树 ********************************************************/ #include<iostream> #include<queue> using namespace std; const int maxn = 100; int prev_[maxn]; int vexs[maxn]; int n;//顶点数 int m;//边数 struct EdgeNode { int u, v;// u -> v int weight;//边权值 /*对于常量型成员变量和引用型成员变量 此处成员变量都是普通成员变量 哪种方法初始化都行 必须通过初始化化列表的方式进行初始化 在构造函数体内进行赋值的方式是行不通的*/ EdgeNode(const int& u, const int& v, const int& weight) :u(u), v(v), weight(weight) {}//构造函数 bool operator < (const EdgeNode& en) const { return en.weight < this->weight; //最小值优先 建立堆元素升序排列 } }; class UnionFind { public: UnionFind(const int& n); int Find(const int& p); void Union(const int& p, const int& q); }; UnionFind::UnionFind(const int& n) { for (int i = 0; i < n; i++) { prev_[i] = -1;//父节点初始化为-1 } } void UnionFind::Union(const int& p, const int& q) { int x = Find(p); //找到p的祖先为x int y = Find(q); //找到q的祖先为y if (x != y)//不属于同一组 { prev_[y] = x; //p, q 合并到一组 } } int UnionFind::Find(const int& p) { if (prev_[p] == -1) return p;//找到祖先 return Find(prev_[p]); } int LocateVertex(int v) { for (int i = 0; i < n; i++) { if (v == vexs[i]) { return i; } } return -1; } void MinSpanTree_Kruskal(priority_queue<EdgeNode>& pq) { int cnt = 0; UnionFind UF(n); while (!pq.empty() || cnt < n - 1)//MST的边数为 顶点数 - 1 { EdgeNode en = pq.top(); pq.pop(); int u = LocateVertex(en.u);//定位顶点索引 int v = LocateVertex(en.v); int x = UF.Find(u); int y = UF.Find(v); if (x != y) //两个顶点不属于同一组 { UF.Union(x, y);//合并两顶点 cnt++; //加入一条边 cout << "加入边(" << vexs[u] << "," << vexs[v] << "); 边长为" << en.weight << "." << endl; } } } int main() { int u[maxn];//起始点 int v[maxn];//终止点 int w[maxn];//权值 cout << "请输入顶点数(n >= 2):"; cin >> n; cout << "请输入边数(m >= n - 1):"; cin >> m; cout << "请输入边依附的顶点及权值信息:" << endl; for (int i = 0; i < n; i++) { vexs[i] = i + 1; } priority_queue<EdgeNode> pq; for (int i = 0; i < m; i++) { cin >> u[i] >> v[i] >> w[i]; EdgeNode en(u[i], v[i], w[i]); pq.push(en);//建立小顶堆 边按权值进行升序排列 } MinSpanTree_Kruskal(pq); return 0; }

输出结果

请输入顶点数(n >= 2):6 请输入边数(m >= n - 1):10 请输入边依附的顶点及权值信息: 1 2 6 1 3 1 1 4 5 2 3 5 2 5 3 3 4 5 3 5 6 5 6 6 3 6 4 4 6 2 加入边(1,3); 边长为1. 加入边(4,6); 边长为2. 加入边(2,5); 边长为3. 加入边(3,6); 边长为4. 加入边(2,3); 边长为5.