常用的两种求最小生成树的算法是Prim算法和Kruskal算法，这里对个算法做一个总结。

Prim算法：只可以用于连通图，当图中存在不连通的点时，此算法不适用。
Kruskal算法：可以用于非连通图，这种情况下求出来的是各个子连通图的最小生成树。

Prim算法

算法描述

Prim算法和Dijkstra算法很相似：
1.初始化一个空集合和一个记录数组，并从一个顶点出发，将这个顶点加入集合中；
2.然后寻找与这个顶点之间距离最近（权值最低）的且没有在集合中的点，将寻找到的点加入集合，并使用这个点的数据对记录数组进行更新；
3.以新加入的点作为顶点重复步骤2，直到所有的顶点都在集合中。

不同之处在于，Dijstra算法中记录数组记录的是其余点到出发顶点的最短距离，而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
#include <iostream>
#define INF 999999

using namespace std;

int dic[1001][1001];
int D[1001];
int visit[1001];

void joinEdge(int e1, int e2, int v) {
	dic[e1][e2] = v;
	dic[e2][e1] = v;
}

int main() {
	int n, m, ans = 0;
	int e1, e2, v;

	cin >> n >> m;

	for (int i = 0; i < n; ++i) {//初始化
		D[i] = INF;
		for (int j = i+1; j < n; ++j) {//除了顶点自身，其余顶点之间的距离为无限大
			if (i == j) dic[i][i] = 0;
			else {
				dic[i][j] = INF;
				dic[j][i] = INF;
			}
		}
	}
	D[0] = 0;//以顶点0为初始顶点

	while (m--) {
		cin >> e1 >> e2 >> v;
		--e1;
		--e2;
		joinEdge(e1, e2, v);
	}

	int minEdges = INF;
	int minNode;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (!visit[j] && D[j] < minEdges) {
				minEdges = D[j];
				minNode = j;
			}
		}
		visit[minNode] = 1;
		ans += minEdges;
		for (int j = 1; j < n; ++j) {
			if (!visit[j] && dic[minNode][j] < D[j])
				D[j] = dic[minNode][j];
		}
		minEdges = INF;
	}

	cout << "最小生成树边的权值和为：" << ans << " " << endl;

	return 0;
}

images

Kruskal算法

算法描述

不同于Prim算法，Kruskal算法是从边出发的。在这里使用并查集能较简单的实现Kruskal算法。首先初始化一个大小为顶点数的并查集，然后对图中的所有边按升序排序。（如果需要判断连通分支数量，可以初始化一个数值为顶点数目的变量）从权值最小的边开始，遍历所有的边。
如果某条边的两个顶点不在同一个集合中，那么就可以将这两个顶点加入同一个集合，并且这条边就是最小生成树中的一条，（然后对记录连通分支数量的变量减一）
如果某条边的两个顶点在同一个集合中，那么跳过这条边，继续遍历后面的边。

例题描述

对有n个顶点、m条边的无向图，计算其最小生成树并输出树的权重，即构成最小生成树的所有边的权重值总和。如果无向图连通，计算结果是一个含(n−1)条边的最小生成树；如果图不连通，则依次计算各个连通子图的最小生成树，再将所有树的权重相加。

输入格式:
第一行给出正整数n(≤1000)和m(≤10000)，分别表示无向图的顶点和边的数量。接下来m行数据，每行给出三个非负整数，分别表示两个顶点编号以及这两个顶点之间边的权值。

输出格式:
在一行中输出两个整数，用空格分开。第一个整数表示无向图的最小生成树的权重，第二个整数是图中连通子图的数量（如果图连通，则输出1）。

输入样例1:
5 5
0 1 1
1 2 1
2 3 1
3 4 1
0 4 2

输出样例1:
4 1

输入样例2:
5 2
0 1 1
2 3 1

输出样例2:
2 3

代码实现

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
#include <iostream>
#include <map>
#include <vector>

using namespace std;
map<int, vector<pair<int, int>>> edges;

class Union {
	vector<int> pre;
public:
	Union(int n) {
		pre.resize(n);
		for(int i=0; i<n; ++i)
			pre[i] = i;
	}
	int search(int node) {
		int temp, root;
		root = node;
		while(root != pre[root])
			root = pre[root];
		while(node != root) {
			temp = pre[node];
			pre[node] = root;
			node = temp;
		}
		return root;
	}
	void join(int x, int y) {
		int root1 = search(x);
		int root2 = search(y);
		if(root1 != root2)
			pre[root2] = root1;
	}
	bool isConnect(int x, int y) {
		return search(x) == search(y);
	}
};

int main() {
	int n, m, ans = 0;
	int e1, e2, v;
	cin >> n >> m;
	Union set(n);
	while (m--) {
		cin >> e1 >> e2 >> v;
		edges[v].push_back(make_pair(e1, e2));
	}
	for (auto i = edges.begin(); i != edges.end(); ++i) {
		for (int j = 0; j < (*i).second.size(); ++j) {
			int x = (*i).second[j].first, y = (*i).second[j].second;
			if (!set.isConnect(x, y)) {
				set.join(x, y);
				ans += (*i).first;
				--n;
			}
		}
	}
	cout << ans << " " << n << endl;

	return 0;
}

images

images