C++使用Kruskal和Prim算法实现最小生成树

C++使用使用Kruskal和和Prim算法实现最小生成树算法实现最小生成树

主要介绍了C++使用Kruskal和Prim算法实现最小生成树，具有一定的参考价值，感兴趣的小伙伴们可以参考一

下

很久以前就学过最小生成树之Kruskal和Prim算法，这两个算法很容易理解，但实现起来并不那么容易。最近学习了并查集算

法，得知并查集可以用于实现上述两个算法后，我自己动手实现了最小生成树算法。

宏观上讲，Kruskal算法就是一个合并的过程，而Prim算法是一个吞并的过程，另外在Prim算法中还用到了一种数据结构——

优先级队列，用于动态排序。由于这两个算法很容易理解，在此不再赘述。接下来给出我的源代码。

输入输入

#include <vector>

#include <algorithm>

#include <fstream>

using namespace std;

struct Edge

{

int u; //边连接的一个顶点编号

int v; //边连接另一个顶点编号

int 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;

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]);

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()