最小生成树Minimum Spanning Tree
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。
树: 无回路
|V|个顶点，一定有|V|-1条边
生成树: 包含全部顶点
|V|-1 条边都在图里
边权重和最小
最小生成树存在<--->图联通
向生成树中任加一条边都一定构成回路
贪心算法
“贪”：每一步都要最好的
“好”：权重最小的边
需要约束：
①只能用图里有的边
②只能正好用掉|V|-1条边
③不能有回路
Prim算法— 让一棵小树长大
| 步骤 | |
| 1 | 任意选取v1为顶点开始，并将v1收录进MST |
| 2 | v1有三条边，选取最短边(v1,v4)为1，并将v4收录进MST |
| 3 | MST={v1,v4}的边中在选取最小的(v1,v2)为2，将v2收录进MST |
| 4 | MST={v1,v4,v2}，选(v4,v3)为2，将v3收录进MST |
| 5 | 不能选(v4,v2)3，会构成回路。所以接着选(v4,v7)4，将v7收录进MST |
| 6 | 选(v7,v6)为1，将v6收录进MST |
| 7 | (v7,v5)6，将v7收录进MST |
T = O(|V|^2) ---稠密图合算
1 /* 邻接矩阵存储 - Prim最小生成树算法 */View Code
2
3 Vertex FindMinDist( MGraph Graph, WeightType dist[] )
4 { /* 返回未被收录顶点中dist最小者 */
5 Vertex MinV, V;
6 WeightType MinDist = INFINITY;
7
8 for (V=0; V<Graph->Nv; V++) {
9 if ( dist[V]!=0 && dist[V]<MinDist) {
10 /* 若V未被收录，且dist[V]更小 */
11 MinDist = dist[V]; /* 更新最小距离 */
12 MinV = V; /* 更新对应顶点 */
13 }
14 }
15 if (MinDist < INFINITY) /* 若找到最小dist */
16 return MinV; /* 返回对应的顶点下标 */
17 else return ERROR; /* 若这样的顶点不存在，返回-1作为标记 */
18 }
19
20 /* 将最小生成树保存为邻接表存储的图MST，返回最小权重和 */
21 int Prim( MGraph Graph, LGraph MST )
22 {
23 WeightType dist[MaxVertexNum], TotalWeight;
24 Vertex parent[MaxVertexNum], V, W;
25 int VCount;
26 Edge E;
27
28 /* 初始化。默认初始点下标是0 */
29 for (V=0; V<Graph->Nv; V++) {
30 /* 这里假设若V到W没有直接的边，则Graph->G[V][W]定义为INFINITY */
31 dist[V] = Graph->G[0][V];
32 parent[V] = 0; /* 暂且定义所有顶点的父结点都是初始点0 */
33 }
34 TotalWeight = 0; /* 初始化权重和 */
35 VCount = 0; /* 初始化收录的顶点数 */
36 /* 创建包含所有顶点但没有边的图。注意用邻接表版本 */
37 MST = CreateGraph(Graph->Nv);
38 E = (Edge)malloc( sizeof(struct ENode) ); /* 建立空的边结点 */
39
40 /* 将初始点0收录进MST */
41 dist[0] = 0;
42 VCount ++;
43 parent[0] = -1; /* 当前树根是0 */
44
45 while (1) {
46 V = FindMinDist( Graph, dist );
47 /* V = 未被收录顶点中dist最小者 */
48 if ( V==ERROR ) /* 若这样的V不存在 */
49 break; /* 算法结束 */
50
51 /* 将V及相应的边<parent[V], V>收录进MST */
52 E->V1 = parent[V];
53 E->V2 = V;
54 E->Weight = dist[V];
55 InsertEdge( MST, E );
56 TotalWeight += dist[V];
57 dist[V] = 0;
58 VCount++;
59
60 for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
61 if ( dist[W]!=0 && Graph->G[V][W]<INFINITY ) {
62 /* 若W是V的邻接点并且未被收录 */
63 if ( Graph->G[V][W] < dist[W] ) {
64 /* 若收录V使得dist[W]变小 */
65 dist[W] = Graph->G[V][W]; /* 更新dist[W] */
66 parent[W] = V; /* 更新树 */
67 }
68 }
69 } /* while结束*/
70 if ( VCount < Graph->Nv ) /* MST中收的顶点不到|V|个 */
71 TotalWeight = ERROR;
72 return TotalWeight; /* 算法执行完毕，返回最小权重和或错误标记 */
73 }
Kruskal算法— 将森林合并成树
| 步骤 | |
| 1 | 选取一条最小边(v1,v4)为1 |
| 2 | 选取一条最小边(v6,v7)为1 |
| 3 | 选取一条最小边(v1,v2)为2 |
| 4 | 选取一条最小边(v3,v4)为2 |
| 5 | 不能选取最小边(v2,v4)3会构成回路 |
| 6 | 选取一条最小边(v7,v4)为4 |
| 7 | 选取一条最小边(v5,v7)为6 |
T= O(|E|log|E|)
1 /* 邻接表存储 - Kruskal最小生成树算法 */View Code
2
3 /*-------------------- 顶点并查集定义 --------------------*/
4 typedef Vertex ElementType; /* 默认元素可以用非负整数表示 */
5 typedef Vertex SetName; /* 默认用根结点的下标作为集合名称 */
6 typedef ElementType SetType[MaxVertexNum]; /* 假设集合元素下标从0开始 */
7
8 void InitializeVSet( SetType S, int N )
9 { /* 初始化并查集 */
10 ElementType X;
11
12 for ( X=0; X<N; X++ ) S[X] = -1;
13 }
14
15 void Union( SetType S, SetName Root1, SetName Root2 )
16 { /* 这里默认Root1和Root2是不同集合的根结点 */
17 /* 保证小集合并入大集合 */
18 if ( S[Root2] < S[Root1] ) { /* 如果集合2比较大 */
19 S[Root2] += S[Root1]; /* 集合1并入集合2 */
20 S[Root1] = Root2;
21 }
22 else { /* 如果集合1比较大 */
23 S[Root1] += S[Root2]; /* 集合2并入集合1 */
24 S[Root2] = Root1;
25 }
26 }
27
28 SetName Find( SetType S, ElementType X )
29 { /* 默认集合元素全部初始化为-1 */
30 if ( S[X] < 0 ) /* 找到集合的根 */
31 return X;
32 else
33 return S[X] = Find( S, S[X] ); /* 路径压缩 */
34 }
35
36 bool CheckCycle( SetType VSet, Vertex V1, Vertex V2 )
37 { /* 检查连接V1和V2的边是否在现有的最小生成树子集中构成回路 */
38 Vertex Root1, Root2;
39
40 Root1 = Find( VSet, V1 ); /* 得到V1所属的连通集名称 */
41 Root2 = Find( VSet, V2 ); /* 得到V2所属的连通集名称 */
42
43 if( Root1==Root2 ) /* 若V1和V2已经连通，则该边不能要 */
44 return false;
45 else { /* 否则该边可以被收集，同时将V1和V2并入同一连通集 */
46 Union( VSet, Root1, Root2 );
47 return true;
48 }
49 }
50 /*-------------------- 并查集定义结束 --------------------*/
51
52 /*-------------------- 边的最小堆定义 --------------------*/
53 void PercDown( Edge ESet, int p, int N )
54 { /* 改编代码4.24的PercDown( MaxHeap H, int p ) */
55 /* 将N个元素的边数组中以ESet[p]为根的子堆调整为关于Weight的最小堆 */
56 int Parent, Child;
57 struct ENode X;
58
59 X = ESet[p]; /* 取出根结点存放的值 */
60 for( Parent=p; (Parent*2+1)<N; Parent=Child ) {
61 Child = Parent * 2 + 1;
62 if( (Child!=N-1) && (ESet[Child].Weight>ESet[Child+1].Weight) )
63 Child++; /* Child指向左右子结点的较小者 */
64 if( X.Weight <= ESet[Child].Weight ) break; /* 找到了合适位置 */
65 else /* 下滤X */
66 ESet[Parent] = ESet[Child];
67 }
68 ESet[Parent] = X;
69 }
70
71 void InitializeESet( LGraph Graph, Edge ESet )
72 { /* 将图的边存入数组ESet，并且初始化为最小堆 */
73 Vertex V;
74 PtrToAdjVNode W;
75 int ECount;
76
77 /* 将图的边存入数组ESet */
78 ECount = 0;
79 for ( V=0; V<Graph->Nv; V++ )
80 for ( W=Graph->G[V].FirstEdge; W; W=W->Next )
81 if ( V < W->AdjV ) { /* 避免重复录入无向图的边，只收V1<V2的边 */
82 ESet[ECount].V1 = V;
83 ESet[ECount].V2 = W->AdjV;
84 ESet[ECount++].Weight = W->Weight;
85 }
86 /* 初始化为最小堆 */
87 for ( ECount=Graph->Ne/2; ECount>=0; ECount-- )
88 PercDown( ESet, ECount, Graph->Ne );
89 }
90
91 int GetEdge( Edge ESet, int CurrentSize )
92 { /* 给定当前堆的大小CurrentSize，将当前最小边位置弹出并调整堆 */
93
94 /* 将最小边与当前堆的最后一个位置的边交换 */
95 Swap( &ESet[0], &ESet[CurrentSize-1]);
96 /* 将剩下的边继续调整成最小堆 */
97 PercDown( ESet, 0, CurrentSize-1 );
98
99 return CurrentSize-1; /* 返回最小边所在位置 */
100 }
101 /*-------------------- 最小堆定义结束 --------------------*/
102
103
104 int Kruskal( LGraph Graph, LGraph MST )
105 { /* 将最小生成树保存为邻接表存储的图MST，返回最小权重和 */
106 WeightType TotalWeight;
107 int ECount, NextEdge;
108 SetType VSet; /* 顶点数组 */
109 Edge ESet; /* 边数组 */
110
111 InitializeVSet( VSet, Graph->Nv ); /* 初始化顶点并查集 */
112 ESet = (Edge)malloc( sizeof(struct ENode)*Graph->Ne );
113 InitializeESet( Graph, ESet ); /* 初始化边的最小堆 */
114 /* 创建包含所有顶点但没有边的图。注意用邻接表版本 */
115 MST = CreateGraph(Graph->Nv);
116 TotalWeight = 0; /* 初始化权重和 */
117 ECount = 0; /* 初始化收录的边数 */
118
119 NextEdge = Graph->Ne; /* 原始边集的规模 */
120 while ( ECount < Graph->Nv-1 ) { /* 当收集的边不足以构成树时 */
121 NextEdge = GetEdge( ESet, NextEdge ); /* 从边集中得到最小边的位置 */
122 if (NextEdge < 0) /* 边集已空 */
123 break;
124 /* 如果该边的加入不构成回路，即两端结点不属于同一连通集 */
125 if ( CheckCycle( VSet, ESet[NextEdge].V1, ESet[NextEdge].V2 )==true ) {
126 /* 将该边插入MST */
127 InsertEdge( MST, ESet+NextEdge );
128 TotalWeight += ESet[NextEdge].Weight; /* 累计权重 */
129 ECount++; /* 生成树中边数加1 */
130 }
131 }
132 if ( ECount < Graph->Nv-1 )
133 TotalWeight = -1; /* 设置错误标记，表示生成树不存在 */
134
135 return TotalWeight;
136 }