189 8069 5689
这篇文章主要讲解了C++使用Kruskal和Prim算法实现最小生成树的方法，内容清晰明了，对此有兴趣的小伙伴可以学习一下，相信大家阅读完之后会有帮助。
很久以前就学过最小生成树之Kruskal和Prim算法，这两个算法很容易理解，但实现起来并不那么容易。最近学习了并查集算法，得知并查集可以用于实现上述两个算法后，我自己动手实现了最小生成树算法。
宏观上讲，Kruskal算法就是一个合并的过程，而Prim算法是一个吞并的过程，另外在Prim算法中还用到了一种数据结构——优先级队列，用于动态排序。由于这两个算法很容易理解，在此不再赘述。接下来给出我的源代码。
输入
第一行包含两个整数n和m，n表示图中结点个数，m表示图中边的条数；接下来m行，每一行包含三个整数u,v,w，表示途中存在一条边(u,v)，并且其权重为w；为了便于调试，我的程序是从文件中输入数据的；
输出
输出程序选择的最小生成树的权值之和以及每一条边信息；
Kruskal算法：
#include#include #include #include using namespace std; struct Edge { int u; //边连接的一个顶点编号 int v; //边连接另一个顶点编号 int w; //边的权值 friend bool operator<(const Edge& E1, const Edge& E2) { return E1.w < E2.w; } }; //创建并查集 void MakeSet(vector & uset, int n) { uset.assign(n, 0); for (int i = 0; i < n; i++) uset[i] = i; } //查找当前元素所在集合的代表元 int FindSet(vector & uset, int u) { int i = u; while (uset[i] != i) i = uset[i]; return i; } void Kruskal(const vector & edges, int n) { vector uset; vector SpanTree; int Cost = 0, e1, e2; MakeSet(uset, n); for (int i = 0; i < edges.size(); i++) //按权值从小到大的顺序取边 { e1 = FindSet(uset, edges[i].u); e2 = FindSet(uset, edges[i].v); if (e1 != e2) //若当前边连接的两个结点在不同集合中，选取该边并合并这两个集合 { SpanTree.push_back(edges[i]); Cost += edges[i].w; uset[e1] = e2; //合并当前边连接的两个顶点所在集合 } } cout << "Result:\n"; cout << "Cost: " << Cost << endl; cout << "Edges:\n"; for (int j = 0; j < SpanTree.size(); j++) cout << SpanTree[j].u << " " << SpanTree[j].v << " " << SpanTree[j].w << endl; cout << endl; } int main() { ifstream in("data.txt"); int n, m; in >> n >> m; vector edges; edges.assign(m, Edge()); for (int i = 0; i < m; i++) in >> edges[i].u >> edges[i].v >> edges[i].w; sort(edges.begin(), edges.end()); //排序之后，可以以边权值从小到大的顺序选取边 Kruskal(edges, n); in.close(); system("pause"); return 0; }
另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。