很久以前就学过最小生成树之Kruskal和Prim算法，这两个算法很容易理解，但实现起来并不那么容易。最近学习了并查集算法，得知并查集可以用于实现上述两个算法后，我自己动手实现了最小生成树算法。
宏观上讲，Kruskal算法就是一个合并的过程，而Prim算法是一个吞并的过程，另外在Prim算法中还用到了一种数据结构——优先级队列，用于动态排序。由于这两个算法很容易理解，在此不再赘述。接下来给出我的源代码。
输入
第一行包含两个整数n和m，n表示图中结点个数，m表示图中边的条数；接下来m行，每一行包含三个整数u,v,w，表示途中存在一条边(u,v)，并且其权重为w；为了便于调试，我的程序是从文件中输入数据的；
输出
输出程序选择的最小生成树的权值之和以及每一条边信息；
Kruskal算法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
#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算法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
#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算法更容易，代码更易于理解。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/lrgdongnan/article/details/51706394
