很久以前就學(xué)過最小生成樹之Kruskal和Prim算法，這兩個(gè)算法很容易理解，但實(shí)現(xiàn)起來并不那么容易。最近學(xué)習(xí)了并查集算法，得知并查集可以用于實(shí)現(xiàn)上述兩個(gè)算法后，我自己動(dòng)手實(shí)現(xiàn)了最小生成樹算法。
宏觀上講，Kruskal算法就是一個(gè)合并的過程，而Prim算法是一個(gè)吞并的過程，另外在Prim算法中還用到了一種數(shù)據(jù)結(jié)構(gòu)――優(yōu)先級(jí)隊(duì)列，用于動(dòng)態(tài)排序。由于這兩個(gè)算法很容易理解，在此不再贅述。接下來給出我的源代碼。
輸入
第一行包含兩個(gè)整數(shù)n和m，n表示圖中結(jié)點(diǎn)個(gè)數(shù)，m表示圖中邊的條數(shù)；接下來m行，每一行包含三個(gè)整數(shù)u,v,w，表示途中存在一條邊(u,v)，并且其權(quán)重為w；為了便于調(diào)試，我的程序是從文件中輸入數(shù)據(jù)的；
輸出
輸出程序選擇的最小生成樹的權(quán)值之和以及每一條邊信息；
Kruskal算法：
#include <iostream>#include <vector>#include <algorithm>#include <fstream>using namespace std; struct Edge{ int u; //邊連接的一個(gè)頂點(diǎn)編號(hào) int v; //邊連接另一個(gè)頂點(diǎn)編號(hào) 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;}//查找當(dāng)前元素所在集合的代表元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) //若當(dāng)前邊連接的兩個(gè)結(jié)點(diǎn)在不同集合中，選取該邊并合并這兩個(gè)集合 { SpanTree.push_back(edges[i]); Cost += edges[i].w; uset[e1] = e2; //合并當(dāng)前邊連接的兩個(gè)頂點(diǎn)所在集合 } } 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;}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; //用于統(tǒng)計(jì)最小生成樹的權(quán)值之和 vector<Edge> SpanTree; //用于保存最小生成樹的邊 vector<int> uset(n,0); //用數(shù)組來實(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算法，開始時(shí)選取結(jié)點(diǎn)0，并將結(jié)點(diǎn)0與剩余部分的邊保存在優(yōu)先隊(duì)列中 //循環(huán)中每次選取優(yōu)先隊(duì)列中權(quán)值最小的邊，并更新優(yōu)先隊(duì)列 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;}就實(shí)現(xiàn)而言，Kruskal算法比Prim算法更容易，代碼更易于理解。
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持武林網(wǎng)。
新聞熱點(diǎn)
疑難解答
