1 简介
给定一个无向图,如果它任意两个顶点都联通并且是一棵树,那么我们就称之为生成树(Spanning Tree)。如果是带权值的无向图,那么权值之和最小的生成树,我们就称之为最小生成树(MST, Minimum Spanning Tree)。
常见求解最小生成树的算法有Kruskal算法和Prim算法,两者都是运用贪心的思路。两者区别:Prim在稠密图中比Kruskal优,在稀疏图(一般我们认为满足E < V ∗ ( V − 1 ) / 4 E < V*(V-1)/4 E < V ∗ ( V − 1 ) / 4 )中比Kruskal劣;Prim是以更新过的节点的连边找最小值,Kruskal是直接将边排序。
注意 :
最小生成树可能有多个,但边的权值之和总是唯一且最小的
最小生成树的边数=顶点数-1
。砍掉一条则不连通,增加一条边则会出现回路
如果一个连通图本身就是一棵树,则其最小生成树就是它本身
只有连通图才有生成树,非连通图只有生成森林
2 Kruskal算法
Kruskal算法是基于贪心的思想得到的。首先我们把所有的边按照权值先从小到大排列,接着按照顺序选取每条边,如果这条边的两个端点不属于同一集合(两点是否连通),那么就将它们合并,直到所有的点都属于同一个集合为止(所有结点连通)。
时间复杂度 :Kruskal算法每次要从都要从剩余的边中选取一个最小的边。通常我们要先对边按权值从小到大排序,这一步的时间复杂度为O ( E l o g E ) O(ElogE) O ( E l o g E ) 。Kruskal算法的实现通常使用并查集,来快速判断两个顶点是否属于同一个集合。最坏的情况可能要枚举完所有的边,此时要循环E E E 次,所以这一步的时间复杂度为O(E*α(V)),其中α为Ackermann函数,其增长非常慢,我们可以视为常数。所以Kruskal算法的时间复杂度为O ( E l o g E ) O(ElogE) O ( E l o g E ) 。
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; 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]); } 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; else { node[root_y] = root_x; if (Rank[root_x] == Rank[root_y]) Rank[root_x]++; } } 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 ( V 2 ) O(V^2) O ( V 2 )
二叉堆、邻接表
O ( ( V + E ) l o g ( V ) ) = O ( E l o g ( V ) ) O((V + E) log(V)) = O(E log(V)) O ( ( V + E ) l o g ( V ) ) = O ( E l o g ( V ) )
斐波那契堆、邻接表
O ( E + V l o g ( V ) ) O(E + V log(V)) O ( E + V l o g ( V ) )
流程 :
输入:一个加权连通图,其中顶点集合为V V V ,边集合为E E E
输出:使用集合V n e w Vnew V n e w 和E n e w Enew E n e w 来描述所得到的最小生成树
从单一顶点开始,Prim算法按照以下步骤逐步扩大树中所含顶点的数目,直到遍及连通图的所有顶点。
初始化:V n e w = x Vnew = {x} V n e w = x ,其中x x x 为集合V V V 中的任一节点(起始点),E n e w = { } Enew = \{\} E n e w = { } ;
重复下列操作,直到V n e w = V Vnew = V V n e w = V :
在集合E E E 中选取权值最小的边( u , v ) (u, v) ( u , v ) ,其中u u u 为集合V n e w Vnew V n e w 中的元素,而v v v 则是V V V 中没有加入V n e w Vnew V n e w 的顶点(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);
将v v v 加入集合V n e w Vnew V n e w 中,将( u , v ) (u, v) ( u , v ) 加入集合E n e w Enew E n e w 中。
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; int g[maxn][maxn]; int dist[maxn]; bool st[maxn]; 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 ; for (int j = 1 ; j <= n; j ++ ) dist[j] = min (dist[j], g[t][j]); } return res; }
练习
牛客——道路建设
牛客——挖沟
Life is painting a picture, not doing a sum.