无向连通图的最小生成树之Prim算法

缘起

【1】中我们引进了无向连通图的生成树的概念. 这里

将介绍最小生成树（MST minimal spanning tree）的概念. 即【1】中介绍的是无向连通图, 而本文准确的说, 介绍的是无向连通网——即在无向生成图的前提下，边是带权重的. 要求出所有生成树中边的权重之和最小的那棵生成树, 就是MST. MST在现实世界显然是有意义的, 例如整个城市要铺设网线, 打通各个城区, 但是两个城市之间铺设光缆的成本是不一样的. 这就是MST大显身手的舞台.

分析

显然, 从任意一个顶点出发，通过dfs搜索（而不是遍历，即isvisited是要改回来的）可以遍历所有的搜索树, 从中取得权重这和最小的就是MST. 这种蛮力算法显然是时间复杂度无法承受的.时间复杂度高达O(n^n), 所以有了如下基于贪心的Prim算法.

Prim算法思考的角度类似于最短路径的dijkstra算法. Prim算法要做的事情就是从任意选取一个顶点出发（随便选, 反正这个点最后是要被加进来的），以最小的代价扩张到整个点集合. 每次扩张仅仅一个点. 那么问题来了, 这个点怎么选? 其实换个角度来看待MST, 令U是已经加入MST的点集, V是尚未加入MST的点集, 则每次扩张的时候, 就是从V中选取一个点加入到U中去. 而选哪个点呢? 当然是选取V中到集合U中最近的那个点. 这就是贪心. 所以为了能快速选取出到U最近的那个点. 我们必须对每个顶点维护其到集合U的距离. 注意, U和V都是在不断变化的, 其中U在不断壮大, V在不断缩小. （因为每次都是从V中选取一个点加入到U中, U伊始只有一个点，就是你伊始任意选取的那个点）. 所以Prim算法的复杂度是O(N^2), 但是因为每次选取到U距离最短的点都是基于比较, 所以根据CBA（comparison-based-algorithm）理论, Prim算法是可以优化到O(NlogN)的，这个后面加入了堆优化再讲. 

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
85
#include "stdafx.h"
#include <iostream>
#include <queue>
#pragma warning(disable:4996)

#define LOCAL
using namespace std;
const int MAX_NUM = 20;
const int INF = 0x3f3f3f3f;


struct Graph
{
	int n; // 顶点的实际个数
	int adj[MAX_NUM][MAX_NUM]; // 邻接矩阵表示法
	int distance[MAX_NUM]; // V中顶点到U的距离数组
	bool isIn[MAX_NUM];// 是否已经加入到MST中去
	int neighbor[MAX_NUM]; // neighbor[i] = j 表示是j将i拉入U中去的. 这个数组的作用是确定最后MST由哪些边组成

	Graph()
	{
		memset(adj, 0x3f, sizeof(adj)); // 全部最大
		memset(isIn, 0,sizeof(isIn));
		isIn[1] = true; // 1这个顶点在MST中
		puts("输入顶点的个数");
		scanf("%d", &n);
		puts("输入各边及其权重");
		int x,y,w;
		while(~scanf("%d%d%d", &x, &y, &w)) adj[x][y] = adj[y][x] = w;
		for (int i = 2; i<=n; i++)
		{
			distance[i] = adj[1][i]; // 初始化V到U的距离
			neighbor[i] = 1; // 伊始都是1将其拉入MST
		}
	}

	int prim() // prim算法得到MST，算法用到了2个选择排序, 这就是堆优化的契机
	{
		int cost = 0; // 总花销
		int m = n-1;
		while(m--) // 每次拉进一个点入MST
		{
			int _min = 0; // 选择拉谁入MST
			int mindistance = INF;
			for (int i = 2; i<=n;i++) if (!isIn[i] && mindistance>distance[i]) mindistance = distance[_min = i];
			isIn[_min] = true; // _min 加入MST
			cost += mindistance;
			for (int i = 2; i<=n;i++)  // 最后发现还是要把 _min 拉入MST , 然后来更新distance, 以及决定neighbor
			{
				if (!isIn[i] && distance[i] > adj[i][_min])
				{
					distance[i] = adj[i][_min];
					neighbor[i] = _min;  // 更新neighbor
				}
			}
		}
		puts("MST如下");
		for (int i = 2; i<=n; i++) printf("(%d,%d)\n", i, neighbor[i]);
		return cost;
	}
};

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	Graph g;
	printf("MST总花销为%d\n",g.prim());
	return 0;
}
/*
测试数据
6
3 1 1
3 2 5
3 4 5
3 5 6
3 6 4
1 2 6
2 5 3
5 6 6
6 4 2
1 4 5
*/

上面的算法比较tricky的地方在于, 按照前面所述的思路, 理应确定了_min 之后, 就应该确定是谁拉_min 入MST的, 但是除了1之外第一个入MST的点一定是1拉他入伙的. 其次, 所有的点反正都是要入MST的, 所以更新neighbor就放到了算法的后半部分(即第二个for). 这是没毛病的.

参考

【1】https://yfsyfs.github.io/2019/05/23/%E6%97%A0%E5%90%91%E5%9B%BE%E7%9A%84%E6%90%9C%E7%B4%A2%E6%A0%91%E5%92%8C%E6%A3%AE%E6%9E%97/