C++使用Kruskal和Prim算法实现最小生成树
155 浏览量
2020-08-26
10:18:33
上传
评论 1
收藏 52KB PDF 举报
C++使用使用Kruskal和和Prim算法实现最小生成树算法实现最小生成树
主要介绍了C++使用Kruskal和Prim算法实现最小生成树，具有一定的参考价值，感兴趣的小伙伴们可以参考一
下
很久以前就学过最小生成树之Kruskal和Prim算法，这两个算法很容易理解，但实现起来并不那么容易。最近学习了并查集算
法，得知并查集可以用于实现上述两个算法后，我自己动手实现了最小生成树算法。
宏观上讲，Kruskal算法就是一个合并的过程，而Prim算法是一个吞并的过程，另外在Prim算法中还用到了一种数据结构——
优先级队列，用于动态排序。由于这两个算法很容易理解，在此不再赘述。接下来给出我的源代码。
输入输入
第一行包含两个整数n和m，n表示图中结点个数，m表示图中边的条数；接下来m行，每一行包含三个整数u,v,w，表示途中存
在一条边(u,v)，并且其权重为w；为了便于调试，我的程序是从文件中输入数据的；
输出输出
输出程序选择的最小生成树的权值之和以及每一条边信息；
Kruskal算法：
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
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<int>& uset, int n)
{
uset.assign(n, 0);
for (int i = 0; i < n; i++)
uset[i] = i;
}
//查找当前元素所在集合的代表元
int FindSet(vector<int>& uset, int u)
{
int i = u;
while (uset[i] != i) i = uset[i];
return i;
}
void Kruskal(const vector<Edge>& edges, int n)
{
vector<int> uset;
vector<Edge> 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:";
cout << "Cost: " << Cost << endl;
cout << "Edges:";
for (int j = 0; j < SpanTree.size(); j++)
cout << SpanTree[j].u << " " << SpanTree[j].v << " " << SpanTree[j].w << endl;
cout << endl;
}
int main()
资源评论
