基于Union-Find的Kruskal算法C++实现

/****************** Kruskal_UnionFind.cpp******************* 功能:使用并查集来实现Kruskal算法求取拓扑图的最小生成树 输入:拓扑图顶点数、边数、各边权值 输出:选取的边及其权重、生成树总权值 ************************************************************/ #include "stdafx.h" #include <iostream> #include <algorithm> #include <cstdio> #include <vector> using namespace std; /********************edge结构体类************************ 数据成员: u,v:边<u,v>的两个端点 w:权值 成员函数: bool operator < (const edge & a)const:小于号重载 比较边的权值w,小于等于则返回true，用于边排序 edgeprint():打印边及权值 *********************************************************/ struct edge { //u,v为边的端点，w为边的权值 int u,v,w; // 小于号 < 运算符重载 bool operator < (const edge & a) const { return w < a.w; } //打印边及权值 void edgePrint() { cout << u << " " << v << " " << w << endl; } }; /********************UnionFind类************************************** 设计思路: 将属于同一个集合的节点看做一棵树，树根的父节点设置为一个负数, 负数的绝对值表示该树的节点数目，Tset中下标为i的元素表示编号为 i的顶点的父节点，初始化值为-1。 数据成员: Tset:存储各节点父节点的向量 成员函数: Find(int):查找节点所在树的根节点，并对树的结构进行路径优化； Union(int,int):将两个节点所在的树合并，将节点少的树挂到节点 多的树上以降低树的深度。 SameRoot(edge):判断边的两个节点是否在同一棵树上,在则返回true。 *********************************************************************/ class UnionFind { public: UnionFind(int len); ~UnionFind(); int Find(int elem); void Union(int R1, int R2); bool SameRoot(edge t); private: vector <int> Tset; }; //构造函数，初始化并查集 UnionFind::UnionFind(int len) { Tset.resize(len + 1, -1); } UnionFind::~UnionFind(){} //返回elem顶点所在树的根节点 int UnionFind::Find(int elem) { if (Tset[elem] < 0) return elem; else return Tset[elem] = Find(Tset[elem]); } //合并R1和R2两个顶点所在的树 void UnionFind::Union(int R1, int R2) { int r1 = Find(R1), r2 = Find(R2); int min1 = min(r1, r2), max1 = max(r1, r2); if (min1 != max1) { Tset[min1] += Tset[max1]; Tset[max1] = min1; } } //判断边t两端点是否在同一棵树 bool UnionFind::SameRoot(edge t) { if (Find(t.u) == Find(t.v)) return true; return false; } /*************************Graph类*********************************** 数据成员: 节点数n，边数m，存储边的向量Edge 成员函数: GraphRead():边的读取 EdgeSort():将边按权值递增排序 nGet():返回节点数n mGet():返回边数m eGet(int):返回向量Edge中下标为i的边Edge[i] ********************************************************************/ class Graph { public: Graph(); ~Graph(); void GraphRead(); void EdgeSort(); int nGet(){ return n;} int mGet(){ return m;} edge eGet(int i){ return Edge[i];} private: vector <edge> Edge; int n, m; }; Graph::Graph(){} Graph::~Graph(){} //读取拓扑图 void Graph::GraphRead() { edge temp; cin >> n >> m; for(int i=0;i<m;i++) { scanf("%d %d %d\n", &temp.u, &temp.v, &temp.w); //去除自环边，重边不影响总权值 if (temp.u != temp.v) Edge.push_back(temp); } } //将边按权值排序 void Graph::EdgeSort() { sort(Edge.begin(), Edge.end()); } /*****************************Kruskal******************************* 算法实现步骤 1、获取拓扑图的信息map1； 2、创建并查集set1，并排序； 3、选取权值最小的边； 4、判断边的端点是否在同一棵树，不在则将该边加入生成树并合并端点 所在树，累加权值，打印选择的边； 5、判断当前已选择的边数是否大于等于节点数-1，如小于则重复步骤3~5， 反之步骤6； 6、打印总权值和所选的边。 ********************************************************************/ void Kruskal() { vector <int> edge_index; Graph map1; map1.GraphRead();//步骤1 UnionFind set1(map1.nGet());//步骤2 map1.EdgeSort(); long long weight = 0; int flag = 0; for (int i = 0; i < map1.mGet(); i++) { edge temp = map1.eGet(i);//步骤3 if (!set1.SameRoot(temp))//步骤4 { flag++; weight += temp.w; edge_index.push_back(i); set1.Union(temp.u, temp.v); } //n个结点的树有且仅有n-1条边 if (flag >= map1.nGet() - 1)//步骤5 break; } cout << weight << endl;//步骤6 for (int i = 0; i < (int)edge_index.size(); i++) map1.eGet(edge_index[i]).edgePrint(); } int main() { freopen("C:\\Users\\10735\\Desktop\\input.txt", "r", stdin); freopen("C:\\Users\\10735\\Desktop\\output.txt", "w", stdout); int ntest; cin >> ntest; while (ntest--) { Kruskal(); if (ntest) cout << endl; } return 0; }