最小生成树_详解(C++描述、Python描述)_生成子树

一、关于树的定义

本定义适用于有根树和无根树

• 森林（forest）：每个连通分量（连通块）都是树的图。按照定义，一棵树也是森林。
• 生成树（spanning tree）：一个连通无向图的生成子图，同时要求是树。也即在图的边集中选择 $n-1$ 条，将所有顶点连通。
• 结点的深度（depth）：到根结点的路径上的边数。
• 树的高度（height）：所有结点的深度的最大值。
• 无根树的叶结点（leaf node）：度数不超过 $1$ 的结点。
• 有根树的叶结点（leaf node）：没有子结点的结点。

以下定义适用于有根树

• 父亲（parent node）：对于除根以外的每个结点，定义为从该结点到根路径上的第二个结点。
  根结点没有父结点。
• 祖先（ancestor）：一个结点到根结点的路径上，除了它本身外的结点。
  根结点的祖先集合为空。
• 子结点（child node）：如果 $u$ 是 $v$ 的父亲，那么 $v$ 是 $u$ 的子结点。
  子结点的顺序一般不加以区分，二叉树是一个例外。
• 兄弟（sibling）：同一个父亲的多个子结点互为兄弟。
• 后代（descendant）：子结点和子结点的后代。
  或者理解成：如果 $u$ 是 $v$ 的祖先，那么 $v$ 是 $u$ 的后代。
• 子树（subtree）：删掉与父亲相连的边后，该结点所在的子图。

在本专题中，我们重点讨论有根树中的生成树

二、生成树、生成森林的定义

1.生成树

什么是生成树？

对连通图进行遍历，过程中所经过的边和顶点的组合可看做是一棵普通树，通常称为生成树我们通过距离来直观的展示生成树的含义。

如下图是一张包含5个结点、5条边的无向图$A$：

我们对这张图进行遍历，根据定义，我们可以得知连通图的生成树必须满足下列两个条件：

1. 包含连通图的所有的节点
2. 任意两顶点间有且仅有一条通路

由于连通图中，由于任意两顶点之间可能含有多条通路，遍历连通图的方式有多种，往往一张连通图可能有多种不同的生成树与之对应。因此对于本图我们可以得到两颗不同的生成树:

我们定义生成树的权为生成树中所有边权的求和，图中$MST-A$的权值为$Q_A=L2+L3+L4+L5$，$MST-B$的权值为$Q_B=L1+L3+L4+L5$

不妨设$Q_A>Q_B$，如果我们想要得到一棵连通所有节点且边权和最小的生成树，显然$Q_B$符合要求，我们称$Q_B$为图$A$的最小生成树。

**Attention！**只有连通图才有生成树，才有最小生成树。而对于非连通图，只存在生成森林。

我们再举一个复杂的图的例子：

本图的最小生成树如右图标红所示。

最小生成树有什么用？

我们举一个现实生活中鲜明生动的例子：修煤气管道(仅仅作示例，实际可能并非如此)

我们拥有一个城镇，城镇的房子之间或有通路，或无通路，现在我们需要修一条煤气管道，由于煤气管道造假高昂，所以要求给出一个方案，保证管道经过每一家每一户而代价最小。经过了对最小生成树的学习，我们不难发现：最优方案便是地图路径连通图的最小生成树。

2.生成森林

生成树是对应连通图而言，而生成森林是对应非连通图而言。

我们知道，非连通图可分解为多个连通分量，而每个连通分量又各自对应多个生成树（至少是 1 棵），因此与整个非连通图相对应的，是由多棵生成树组成的生成森林。

我们给出一张非连通图$B$，其对应的一种生成森林如右所示：

三、最小生成树算法详解(C++描述、Python描述)

我们在讲解的过程中对于图的储存结构全部采用边集的方式进行储存

1.Kruskal’S Algorithm

1.1 核心思想概述

具体的概括：维护一个森林，查询两个结点是否在同一棵树中，并连接两棵树。

反应到算法上的具体体现：维护一堆集合，查询两个元素是否属于同一集合，合并两个集合。

由于涉及到的集合的查询问题，我们可以采用并查集对查询过程进行优化。

1.2 详解

我们继续使用下面这张示例图来讲解Kruskal算法的原理及过程。

我们首先建图，读入边权信息；然后我们对边集按照边权从大到小的顺序进行排序，得到一个有序的边集数组。我们将每个点视为一个独立的连通分量，遍历边集，每次遍历查询两个结点是否位于同一连通分量中(不成环)，对两点选择性进行连接。

我们不难发现，Kruskal算法实际上是个贪心算法的应用。

伪代码描述如下：
1 Input.   The edges of the graph  e ,  where each element in  e  is  ( u , v , w )  denoting that there is an edge between  u  and  v  weighted  w . 2 Output.   The edges of the MST of the input graph . 3 Method.   4 r e s u l t ← ∅ 5 sort  e  into nondecreasing order by weight  w 6 for  each  ( u , v , w )  in the sorted  e 7 if   u  and  v  are not connected in the union-find set  8 connect  u  and  v  in the union-find set 9 r e s u l t ← r e s u l t    ⋃   { ( u , v , w ) } 10 return   r e s u l t

$$\begin{array}{ll} 1 & \textbf{Input. } \text{The edges of the graph } e , \text{ where each element in } e \text{ is } (u, v, w) \\ & \text{ denoting that there is an edge between } u \text{ and } v \text{ weighted } w . \\ 2 & \textbf{Output. } \text{The edges of the MST of the input graph}.\\ 3 & \textbf{Method. } \\ 4 & result \gets \varnothing \\ 5 & \text{sort } e \text{ into nondecreasing order by weight } w \\ 6 & \textbf{for} \text{ each } (u, v, w) \text{ in the sorted } e \\ 7 & \qquad \textbf{if } u \text{ and } v \text{ are not connected in the union-find set } \\ 8 & \qquad\qquad \text{connect } u \text{ and } v \text{ in the union-find set} \\ 9 & \qquad\qquad result \gets result\;\bigcup\ \{(u, v, w)\} \\ 10 & \textbf{return } result \end{array}$$ 12345678910​Input. The edges of the graph e, where each element in e is (u,v,w) denoting that there is an edge between u and v weighted w.Output. The edges of the MST of the input graph.Method. result←∅sort e into nondecreasing order by weight wfor each (u,v,w) in the sorted eif u and v are not connected in the union-find set connect u and v in the union-find setresult←result⋃ {(u,v,w)}return result​
具体的执行过程图解：

1.3 C++描述：Kruskal’s Algorithm

#include <bits/stdc++.h>
#define rnt register int
#define ll long long
using namespace std;
const int N = 2005, M = 1000000;
const int inf = 0x7fffffff;

//定义边结构
typedef struct edge{ int u, v, dis; }edge;

int n, tot = 0;
int px[N], py[N], father[N];
edge edgeset[M];

//定义比较器
inline bool cmp(const edge &a, const edge &b){ return a.dis > b.dis; }

//并查集模板
int get(int x){
    if(father[x] != x) father[x] = get(father[x]);
    return father[x];
}

void kruskal(){
    int u, v, dis, cnt = 0, sum = 0;
    for(rnt i = 1; i <= n; i++) father[i] = i;  //*初始化并查集
    for(rnt i = 1; i <= tot; i++){
        //*查询是否位于同一个集合
        u = edgeset[i].u, v = edgeset[i].v;
        u = get(u), v = get(v);
        if(u != v){
            father[u] = v;
            sum += edgeset[i].dis;
            cnt++;
        }
        if(cnt == n - 1) break;
    }
    if(cnt == n - 1) cout << sum << endl;
    else cout << -1 << endl;
    return;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin >> n;
    //读入数据
    for(rnt i = 1; i <= n; i++)
        cin >> edgeset[i].u >> edgeset[i].v  >> edgeset[i].dis;
    //贪心排序
    sort(edgeset + 1, edgeset + 1 + n, cmp);
    kruskal();
    return 0;
}

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

1.4 Python描述：Kruskal’s Algorithm

我们使用一个下标为顶点编号的表reps记录各顶点的代表元关系。具体的原理同并查集，参考 裘宗燕 《数据结构与算法-Python语言描述》

def kruskal(graph):
    vnum = graph.vertex_num()
    reps = [i for i in range(vnum)]
    mst, edges = [], []
    for vi in range(vnum):                                         										 
        for v, w in graph.out_edges(vi): edges.append((w, vi, v))    # 所有边加入表edges
    edges.sort()                                                    												# 边权排序
    for w, vi, vj in edges:
        if reps[vi] != reps[vj]:                                    											# 两端点属于不同连通分量
            mst.append((vi, vj), w)                                 									  # 记录这条边
            if len(mst) == vnum - 1: break
            rep, orep = reps[vi], reps[vj]
            for i in range(vnum):                                  											 # 合并联通分量
                if reps[i] == orep: reps[i] = rep
    return mst
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
'
运行
运行

1.5 总结

• $Kruskal$算法是一种常见而且好写的最小生成树算法，本质属于贪心算法；
• 基本思想：从小到大加入边
• 适用于稀松图，稠密图应该用$Prim$算法
• 需要前导知识：并查集、贪心算法、图的储存方式
• 如果使用 $O(m\log m)$ 的排序算法，并且使用 $O(m\alpha (m,n))$ 或 $O(m\log n)$ 的并查集，就可以得到时间复杂度为 $O(m\log m)$ 的 Kruskal 算法。

1.6 扩展：证明(引用自OI-WIKI)

思路很简单，为了造出一棵最小生成树，我们从最小边权的边开始，按边权从小到大依次加入，如果某次加边产生了环，就扔掉这条边，直到加入了 $n-1$ 条边，即形成了一棵树。

证明：使用归纳法，证明任何时候 K 算法选择的边集都被某棵 MST 所包含。

基础：对于算法刚开始时，显然成立（最小生成树存在）。

归纳：假设某时刻成立，当前边集为 $F$，令 $T$ 为这棵 MST，考虑下一条加入的边 $e$。

如果 $e$ 属于 $T$，那么成立。

否则，$T+e$ 一定存在一个环，考虑这个环上不属于 $F$ 的另一条边 $f$（一定只有一条）。

首先，$f$ 的权值一定不会比 $e$ 小，不然 $f$ 会在 $e$ 之前被选取。

然后，$f$ 的权值一定不会比 $e$ 大，不然 $T+e-f$ 就是一棵比 $T$ 还优的生成树了。

所以，$T+e-f$ 包含了 $F$，并且也是一棵最小生成树，归纳成立。

2.Prim Algorithm

2.1 核心思想概述

具体的来说，我们每次需要寻找距离最小的一个结点(与Dijkstra’s Algorithm相似)，以及新的边来更新其它结点的距离。在寻找距离最小点的过程中，可以暴力查找，也可以采用堆维护进行优化。

堆优化的方式类似 Dijkstra 的堆优化，但如果使用二叉堆等不支持 $O(1)$ decrease-key 的堆，复杂度就不优于 Kruskal，常数也比 Kruskal 大。所以，一般情况下都使用 Kruskal 算法，在稠密图尤其是完全图上，暴力 Prim 的复杂度比 Kruskal 优，但 不一定 实际跑得更快。

时间复杂度估计：

暴力：$O(n^2+m)$。

二叉堆：$O((n+m)\log n)$。

Fib 堆：$O(n\log n+m)$。

与$Kruskal$ 算法最明显的区别是，$Kruskal$算法初始时拥有一片森林，从点入手对边进行操作；而$Prim$算法则是遍历边集，对点进行操作。这两种算法的入手点不同造成了各自擅长应用场景的不同：稀松图采用$Kruskal$算法进行求解更合适、稠密图则更适合使用$Prim$算法进行求解。

2.2 详细讲解

我们仍然使用下面这张示例图来讲解Prim算法的原理及过程。请注意，为了帮助理解，我们并非描述算法中的逐步过程，具体逐步过程参见"具体执行过程图解"

(从S = 0出发）

1.预备工作：首先我们将所有的结点分成两个集合A和B，A表示在最小生成树中的点，B则表示不在最小生成树中的点；

2.算法初始化：取任意一个结点(这里取$S=0$)加入最小生成树集合$A$，然后遍历集合$B$，选取一个点$v_j$使得$(v,v_j)$的权值最小，然后将$v_j$加入最小生成树集合$A$，并将该结点从集合$B$中移除；

• 目前的出发方案：

这里我们选择边权最小且相等的点$1$和$5$；

3.此时我们的出发路径方案有：

因此选择从3出发，到达结点1：

4.同理，继续列出方案方案扫描，选择1~4之间的边进行连接。

此时列举方案并遍历，发现所有的方案都会构成环路，遍历逐层终止并退出，最小生成树求解完毕

伪代码描述：
1 Input.   The nodes of the graph  V  ; the function  g ( u , v )  which means the weight of the edge  ( u , v ) ; the function  a d j ( v )  which means the nodes adjacent to  v . 2 Output.   The sum of weights of the MST of the input graph. 3 Method. 4 r e s u l t ← 0 5 choose an arbitrary node in  V  to be the  r o o t 6 d i s ( r o o t ) ← 0 7 for   each node  v ∈ ( V − { r o o t } ) 8 d i s ( v ) ← ∞ 9 r e s t ← V 10 while   r e s t ≠ ∅ 11 c u r ← the node with the minimum  d i s  in  r e s t 12 r e s u l t ← r e s u l t + d i s ( c u r ) 13 r e s t ← r e s t − { c u r } 14 for  each node  v ∈ a d j ( c u r ) 15 d i s ( v ) ← min ⁡ ( d i s ( v ) , g ( c u r , v ) ) 16 return   r e s u l t

$$\begin{array}{ll} 1 & \textbf{Input. } \text{The nodes of the graph }V\text{ ; the function }g(u, v)\text{ which}\\ & \text{means the weight of the edge }(u, v)\text{; the function }adj(v)\text{ which}\\ & \text{means the nodes adjacent to }v.\\ 2 & \textbf{Output. } \text{The sum of weights of the MST of the input graph.} \\ 3 & \textbf{Method.} \\ 4 & result \gets 0 \\ 5 & \text{choose an arbitrary node in }V\text{ to be the }root \\ 6 & dis(root)\gets 0 \\ 7 & \textbf{for } \text{each node }v\in(V-\{root\}) \\ 8 & \qquad dis(v)\gets\infty \\ 9 & rest\gets V \\ 10 & \textbf{while } rest\ne\varnothing \\ 11 & \qquad cur\gets \text{the node with the minimum }dis\text{ in }rest \\ 12 & \qquad result\gets result+dis(cur) \\ 13 & \qquad rest\gets rest-\{cur\} \\ 14 & \qquad \textbf{for}\text{ each node }v\in adj(cur) \\ 15 & \qquad\qquad dis(v)\gets\min(dis(v), g(cur, v)) \\ 16 & \textbf{return } result \end{array}$$ 12345678910111213141516​Input. The nodes of the graph V ; the function g(u,v) whichmeans the weight of the edge (u,v); the function adj(v) whichmeans the nodes adjacent to v.Output. The sum of weights of the MST of the input graph.Method.result←0choose an arbitrary node in V to be the rootdis(root)←0for each node v∈(V−{root})dis(v)←∞rest←Vwhile rest​=∅cur←the node with the minimum dis in restresult←result+dis(cur)rest←rest−{cur}for each node v∈adj(cur)dis(v)←min(dis(v),g(cur,v))return result​
具体执行过程图解：

2.3 C++描述：Prim Algorithm

#include <bits/stdc++.h>
#define ri register int 
#define ll long long 
using namespace std;
const int maxn=2005;
const int inf=192681792;
int n,c;
int px[maxn],py[maxn];
struct Edge{
	int ne,to,dis;
}edge[19260817];
int h[maxn],num_edge=0;
struct Ele{
	int ver,dis;
	bool operator <(const Ele &b)const{
		return dis>b.dis;
	}
	Ele(int x,int y){ver=x,dis=y;}
};
inline void add_edge(int f,int t,int dis){
	edge[++num_edge].ne=h[f];
	edge[num_edge].to=t;
	edge[num_edge].dis=dis;
	h[f]=num_edge;
}
inline void prim(){
	priority_queue<Ele>a;
	int d[maxn],u,v,dis,cnt=0,ans=0,q=n-1;
	bool vis[maxn];
	for(ri i=1;i<=n;i++){d[i]=inf,vis[i]=0;}
	d[1]=0;
	while(a.size())a.pop();
    a.push(Ele(1,0));
	while(a.size()){
		u=a.top().ver,dis=a.top().dis,a.pop();
		while(vis[u]){
			u=a.top().ver,dis=a.top().dis,a.pop();
		}
		//ans+=dis,
		cnt++,vis[u]=1;
		//cout<<cnt<<endl;
		if(cnt==n-1)break;
		for(ri i=h[u];i;i=edge[i].ne){
			v=edge[i].to;
			if(!vis[v]&&d[v]>edge[i].dis){
				if(d[v]==inf)q--;
				d[v]=edge[i].dis;
				a.push(Ele(v,d[v]));
			}
		}
		if(q==n-cnt)break;
	}
	for(ri i=1;i<=n;i++)ans+=d[i];
	if(cnt==n-1)printf("%d\n",ans);
	else puts("-1");
	return ;
}
int main(){
	scanf("%d %d",&n,&c);
	for(ri i=1;i<=n;i++){
		scanf("%d %d",&px[i],&py[i]);
		for(ri j=1;j<i;j++){
			int d=(px[i]-px[j])*(px[i]-px[j])+(py[i]-py[j])*(py[i]-py[j]);
			if(d>=c){
				add_edge(i,j,d);
				add_edge(j,i,d);//edge[++tot].u=i,edge[tot].v=j,edge[tot].dis=d;
			}
		}
	}
	prim();
	return 0;
}
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

2.4 Python描述：Prim Algorithm

def Prim(graph, vertex_num):
    INF = 1 << 10
    visit = [False] * vertex_num
    dist = [INF] * vertex_num
    for i in range(vertex_num):
        miniDist = INF + 1
        nextIndex = -1
        for j in range(vertex_num):
            if dist[j] < miniDist and not visit[j]:
                miniDist = dist[j]
                nextIndex = j
        print(nextIndex+1)
        visit[nextIndex] = True
        for j in range(vertex_num):
            if dist[j] > graph[nextIndex][j] and not visit[j]:
                dist[j] = graph[nextIndex][j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
'
运行
运行