溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了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:\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()); //排序之后，可以以邊權值從小到大的順序選取邊
Kruskal(edges, n);
in.close();
system("pause");
return 0;
}Prim算法：
#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; //用于統計最小生成樹的權值之和
vector<Edge> SpanTree; //用于保存最小生成樹的邊
vector<int> uset(n,0); //用數組來實現并查集
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)); //根據Prim算法，開始時選取結點0，并將結點0與剩余部分的邊保存在優先隊列中
//循環中每次選取優先隊列中權值最小的邊，并更新優先隊列
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;
}就實現而言，Kruskal算法比Prim算法更容易，代碼更易于理解。
看完上述內容，是不是對C++使用Kruskal和Prim算法實現最小生成樹的方法有進一步的了解，如果還想學習更多內容，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
