最小生成树

1 简介

给定一个无向图,如果它任意两个顶点都联通并且是一棵树,那么我们就称之为生成树(Spanning Tree)。如果是带权值的无向图,那么权值之和最小的生成树,我们就称之为最小生成树(MST, Minimum Spanning Tree)。

常见求解最小生成树的算法有Kruskal算法和Prim算法,两者都是运用贪心的思路。两者区别:Prim在稠密图中比Kruskal优,在稀疏图(一般我们认为满足E<V(V1)/4E < V*(V-1)/4)中比Kruskal劣;Prim是以更新过的节点的连边找最小值,Kruskal是直接将边排序。

注意

  1. 最小生成树可能有多个,但边的权值之和总是唯一且最小的
  2. 最小生成树的边数=顶点数-1。砍掉一条则不连通,增加一条边则会出现回路
  3. 如果一个连通图本身就是一棵树,则其最小生成树就是它本身
  4. 只有连通图才有生成树,非连通图只有生成森林

2 Kruskal算法

Kruskal算法是基于贪心的思想得到的。首先我们把所有的边按照权值先从小到大排列,接着按照顺序选取每条边,如果这条边的两个端点不属于同一集合(两点是否连通),那么就将它们合并,直到所有的点都属于同一个集合为止(所有结点连通)。

时间复杂度:Kruskal算法每次要从都要从剩余的边中选取一个最小的边。通常我们要先对边按权值从小到大排序,这一步的时间复杂度为O(ElogE)O(ElogE)。Kruskal算法的实现通常使用并查集,来快速判断两个顶点是否属于同一个集合。最坏的情况可能要枚举完所有的边,此时要循环EE次,所以这一步的时间复杂度为O(E*α(V)),其中α为Ackermann函数,其增长非常慢,我们可以视为常数。所以Kruskal算法的时间复杂度为O(ElogE)O(ElogE)

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
const int maxn = 1e5 + 5;
const int maxv = 5e5 + 5;
const int inf = 0x7fffffff;
int n, v; // n是点数,v是边数

struct Edge {// 存储边
int a, b, w;

bool operator< (const Edge &W)const {
return w < W.w;
}
}edges[maxv];

int node[maxn];//并查集的父节点数组
int Rank[maxn];//树的高度

//初始化
void init(int n) {
for (int i=0; i<=n; i++) {
node[i] = i;
Rank[i] = 1;
}
}
//路径压缩
//查找当前元素所在树的根节点(代表元素)
int find(int x) {
if (x == node[x])
return x;
return node[x] = find(node[x]);//在第一次查找时,将节点直连到根节点
}
//按秩合并
//合并x和y所在的集合
void merge(int x, int y) {
int root_x = find(x);//找到根节点
int root_y = find(y);
if (root_x == root_y)//两者根节点相同
return ;
//判断两棵树的高度,然后在决定谁为子树
if (Rank[root_x] < Rank[root_y])
node[root_x] = root_y;//将x的根节点接到y的根节点下
else {
node[root_y] = root_x;//将y的根节点与x的根节点下
if (Rank[root_x] == Rank[root_y])//树的高度相同
Rank[root_x]++;//root_x树高度+1
}
}
//判断xy是否属于一个集合
bool same(int x, int y) {
return find(x) == find(y);
}

int kruskal() {
sort(edges, edges + v);

init(n); // 初始化并查集

int res = 0, cnt = 0;
for (int i = 0; i < v; i ++ ) {
int a = edges[i].a, b = edges[i].b, w = edges[i].w;

a = find(a), b = find(b);
if (a != b) {// 如果两个连通块不连通,
merge(a, b);//则将这两个连通块合并
res += w;
cnt ++ ;
}
}

if (cnt < n - 1) return inf;//原图不连通
return res;
}

3 Prim算法

思想

从某一个顶点开始构建生成树;每次将代价最小的新顶点纳入生成树,直到所有顶点都纳入为止。

时间复杂度

最小边、权的数据结构 时间复杂度(总计)
邻接矩阵、搜索 O(V2)O(V^2)
二叉堆、邻接表 O((V+E)log(V))=O(Elog(V))O((V + E) log(V)) = O(E log(V))
斐波那契堆、邻接表 O(E+Vlog(V))O(E + V log(V))

流程

输入:一个加权连通图,其中顶点集合为VV,边集合为EE
输出:使用集合VnewVnewEnewEnew来描述所得到的最小生成树

从单一顶点开始,Prim算法按照以下步骤逐步扩大树中所含顶点的数目,直到遍及连通图的所有顶点。

  1. 初始化:Vnew=xVnew = {x},其中xx为集合VV中的任一节点(起始点),Enew={}Enew = \{\}
  2. 重复下列操作,直到Vnew=VVnew = V:
    1. 在集合EE中选取权值最小的边(u,v)(u, v),其中uu为集合VnewVnew中的元素,而vv则是VV中没有加入VnewVnew的顶点(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);
    2. vv加入集合VnewVnew中,将(u,v)(u, v)加入集合EnewEnew中。
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
const int maxn = 105;
const int inf = 0x3f3f3f3f;

int n; // n表示点数
int g[maxn][maxn]; // 邻接矩阵,存储所有边,编号从1开始
int dist[maxn]; // 存储其他点到当前最小生成树的距离
bool st[maxn]; // 存储每个点是否已经在生成树中


// 如果图不连通,则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim() {
memset(dist, 0x3f, sizeof dist);

int res = 0;
for (int i = 0; i < n; i ++ ) {
//寻找代价最小的新顶点
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
//原图不连通
if (i && dist[t] == inf) return inf;
//加点
if (i) res += dist[t];
st[t] = true;
//更新dist
for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
}

return res;
}

练习

  1. 牛客——道路建设
  2. 牛客——挖沟