C++使用Kruskal和Prim算法實現(xiàn)最小生成樹的方法

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
 
struct Edge
{
 int u; //邊連接的一個頂點編號
 int v; //邊連接另一個頂點編號
 int w; //邊的權(quán)值
 friend bool operator<(const Edge& E1, const Edge& E2)
 {
 return E1.w < E2.w;
 }
};
//創(chuàng)建并查集
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++) //按權(quán)值從小到大的順序取邊
 {
 e1 = FindSet(uset, edges[i].u);
 e2 = FindSet(uset, edges[i].v);
 if (e1 != e2) //若當前邊連接的兩個結(jié)點在不同集合中，選取該邊并合并這兩個集合
 {
 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<Edge> 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()); //排序之后，可以以邊權(quán)值從小到大的順序選取邊
 Kruskal(edges, n);
 
 in.close();
 
 system("pause");
 return 0;
}

#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
using namespace std;
struct Node
{
 int v;
 int w;
 Node(int a, int b) :v(a), w(b){}
};
struct Edge
{
 int u;
 int v;
 int w;
 Edge(int a, int b, int c) :u(a), v(b), w(c){}
 friend bool operator<(const Edge& E1, const Edge& E2)
 {
 return E1.w>E2.w;
 }
};
int n, m;
vector<list<Node>> Adj;
priority_queue<Edge> Q;
 
int FindSet(vector<int>& uset, int v)
{
 int i = v;
 while (i != uset[i]) i = uset[i];
 return i;
}
 
void Prim()
{
 int Cost = 0; //用于統(tǒng)計最小生成樹的權(quán)值之和
 vector<Edge> SpanTree; //用于保存最小生成樹的邊
 vector<int> uset(n,0); //用數(shù)組來實現(xiàn)并查集
 Edge E(0, 0, 0);
 for (int i = 0; i < n; i++) uset[i] = i; //并查集初始化
 for (auto it = Adj[0].begin(); it != Adj[0].end(); it++) 
 Q.push(Edge(0, it->v, it->w)); //根據(jù)Prim算法，開始時選取結(jié)點0，并將結(jié)點0與剩余部分的邊保存在優(yōu)先隊列中
 //循環(huán)中每次選取優(yōu)先隊列中權(quán)值最小的邊，并更新優(yōu)先隊列
 while (!Q.empty())
 {
 E = Q.top();
 Q.pop();
 if (0 != FindSet(uset, E.v))
 {
 Cost += E.w;
 SpanTree.push_back(E);
 uset[E.v] = E.u;
 for (auto it = Adj[E.v].begin(); it != Adj[E.v].end(); it++)
 if (0 != FindSet(uset, it->v)) Q.push(Edge(E.v, it->v, it->w));
 }
 }
 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 u, v, w;
 in >> n >> m;
 Adj.assign(n, list<Node>());
 for (int i = 0; i < m; i++)
 {
 in >> u >> v >> w;
 Adj[u].push_back(Node(v,w));
 Adj[v].push_back(Node(u,w));
 }
 Prim();
 
 in.close();
 
 system("pause");
 return 0;
}