无向连通图的最小生成树(MST)之Kruskal算法

缘起

【1】中介绍了MST（无向连通图的最小生成树）的概念并给出了Prim算法, 【2】中使用堆结构对Prim算法给出了堆优化. 这里将给出无向连通图的 MST的第二种算法——Kruskal算法

分析

算法基于快排+并查集。 想法很简单——将所有的边从小到大排序，从最短的边开始扫描, 如果发现该边的两个顶点已经在一个连通分支里面了(通过并查集, 所以无向图是否连通亦可以使用并查集算法搞定) 则不需要引入该边到MST中. 否则引入（注意，是以最小的cost引入），所以最后所有的顶点都在一个等价类中了（即都彼此连通）. 所以kruskal算法本质和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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996)
#include <algorithm>

#define LOCAL
using namespace std;
const int MAX_V_NUM = 20; // 图的顶点个数最多
const int MAX_E_NUM = 20; // 图的边的条数最多

struct Graph
{
	Graph()
	{
		puts("输入顶点个数和边的条数");
		cin >> n >> m;
		for (int i = 1; i<=m;i++) cin >> edges[i].x >> edges[i].y >> edges[i].w;
	}

	int kruskal()
	{
		int cost = 0;
		sort(edges+1, edges+m,Edge::cmp); // 边按照权重从小到大进行排序
		memset(f, -1, sizeof(f)); // 初始化并查集数组, 即每个元素伊始都是根节点, 并且每个树上的元素个数都是1
		for (int i = 1; i<=m;i++)
		{
			if (merge(edges[i])) continue; // 如果已经在一起了, 则跳过, 如果不在一起的话, 也做好了并查集的合并
			cost += edges[i].w;
			edges[i].print();
		}
		return cost;
	}

	

private:

	struct Edge
	{
		int x,y,w; // 边的两个顶点和权重
		void print()
		{
			printf("(%d, %d)", x,y);
		}

		static bool cmp(const Edge& a, const Edge& b) // 定义 a<b
		{
			return a.w < b.w;
		}
	};

	int n,m; // 图实际的顶点数和边的数目
	Edge edges[MAX_E_NUM]; // 边集合

	int f[MAX_V_NUM]; // 并查集数组 索引0不用于存储数据, 从1开始

	int getf(int i) {return f[i]<0?i:f[i]=getf(f[i]);} // 找爹，并且进行路径压缩

	bool merge(Edge e) // 判断一条边的2个顶点是否已经在一个连通集中, 如果是, 返回true, 否则返回false
	{
		int r_x = getf(e.x), r_y = getf(e.y);
		if (r_x == r_y) return true; // 如果已经在一棵树中
		if (f[r_x]>f[r_y]) // 如果e.x所在树的顶点个数<e.y所在树的顶点个数的话(注意,如果f[i]<0的话, 表示i是根节点, 并且 -f[i]表示它统领的树的节点总数)， 则为了防止数据倾斜, 要将元素少的并入元素多的(并查集优化)
		{
			f[r_y] += f[r_x];
			f[r_x] = r_y;
		}
		else
		{
			f[r_x] += f[r_y];
			f[r_y] = r_x;
		}
		return false;
	}
};


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	Graph g;
	printf("最小代价是%d\n", g.kruskal());
	return 0;
}
/*
测试数据
6 10
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
*/

从上面的算法知道 kruskal算法的时间复杂度是O(MlogM+MlogN), 其中M是图边的数目, 而N是图顶点的个数. 而一般情况下，图的边的数目比顶点的数目多得多, 所以kruskal算法的时间复杂度是O（MlogM）,即对边进行快排的复杂度. 上面对于并查集的处理和【3】、【4】都不一样. 这里和【3】的目的都是防止数据倾斜的处理. 但是【3】的处理比较古板. 非得建立一个结构体，里面一个域描述根节点，一个描述孩子的数目（这个域仅仅对根节点有效），而这里f[i] = j 如果 j\<0 的话,="" 就表示是根节点,="" 并且="" -f[i]的数值就是该根节点的树的大小（即树上的节点个数）,="" 如果j="">0 则表示它不是根节点, 它(即i)所在树的根节点是j.

实话讲, kruskal算法比prim要简单一些.

参考

【1】https://yfsyfs.github.io/2019/05/25/%E6%97%A0%E5%90%91%E8%BF%9E%E9%80%9A%E5%9B%BE%E7%9A%84%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%E4%B9%8BPrim%E7%AE%97%E6%B3%95/

【2】https://yfsyfs.github.io/2019/05/26/Prim%E7%AE%97%E6%B3%95%E4%B9%8B%E5%A0%86%E4%BC%98%E5%8C%96/

【3】https://yfsyfs.github.io/2019/05/24/%E7%AD%89%E4%BB%B7%E7%B1%BB/

【4】https://yfsyfs.github.io/2019/05/24/%E5%B9%B6%E6%9F%A5%E9%9B%86%E6%A8%A1%E6%9D%BF/