最小生成树&&次小生成树

习题链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=85800#overview

密码xwd

　　关于生成树的定义：设图 G=(V, E) 是个连通图，当从图任一顶点出发遍历图G 时，将边集 E(G) 分成两个集合 T(G) 和 B(G)。其中 T(G)是遍历图时所经过的边的集合，B(G) 是遍历图时未经过的边的集合。显然，G1(V, T) 是图 G 的极小连通子图，即子图G1 是连通图 G 的生成树。

　　生成树的用处很多，下面介绍一下最小生成树。

　　顾名思义，最小生成树即边权和最小的生成树。假如我们在游玩，那么从一个景点出发到其他所有的景点获取最短的路径是很excited的。这就涉及到了最小生成建树的问题。

　　获得最小生成树的算法有很多，其中最常用的是kruskal和prim算法。

　　kruskal算法俗称破圈法，是一个贪心算法的典型例子。kruskal算法的思想是将所有的边排序，紧接着在这些边中取最小权值的边，并判断它双向的点是否连通以及是否成环。这样扫描一遍所有的边即可获得最小生成树。

　　对kruskal算法的证明：

对于一个无向加权连通图，总是存在一棵或以上的有限课生成树，而这些生成树中肯定存在至少一棵最小生成树。下面证明Kruskal算法构造的生成树是这些最小生成树中的一棵。
　　设T为Kruskal算法构造出的生成树，U是G的最小生成树。如果T==U那么证明结束。如果T != U，我们就需要证明T和U的构造代价相同。由于T != U，所以一定存在k > 0条边存在于T中，却不在U中。接下来，我们做k次变换，每次从T中取出一条不在U中的边放入U，然后删除U一条不在T中的边，最后使T和U的边集相同。每次变换中，把T中的一条边e加入U，同时删除U中的一条边f。e、f按如下规则选取：a). e是在T中却不在U中的边的最小的一条边；b). e加入U后，肯定构成唯一的一个环路，令f是这个环路中的一条边，但不在T中。f一定存在，因为T中没有环路。
　　这样的一次变换后，U仍然是一棵生成树。
　　我们假设e权值小于f，这样变换后U的代价一定小于变换前U的代价，而这和我们之前假设U是最小生成树矛盾，因此e权值不小于f。
　　再假设e权值大于f。由于f权值小于e，由Kruskal算法知，f在e之前从E中取出，但被舍弃了。一定是由于和权值小于等于f的边构成了环路。但是T中权值小于等于f（小于e）的边一定存在于U中，而f在U中却没有和它们构成环路，又推出矛盾。所以e权值不大于f。于是e权值等于f。
　　这样，每次变换后U的代价都不变，所以K次变换后，U和T的边集相同，且代价相同，这样就证明了T也是最小生成树。由证明过程可以知道，最小生成树可以不是唯一的。

　　如何判断无向图是否成环？这里介绍一个很巧妙很实用的数据结构：并查集。

顾名思义，并查集是对一个集合进行维护的数据结构，它包含了两种基本操作：并和查（- -）

代码：

 1 int pre[maxn];
 2 int N, d;
 3 
 4 int find(int x) {
 5     return x == pre[x] ? x : pre[x] = find(pre[x]);
 6 }
 7 
 8 void unite(int x, int y) {
 9     x = find(x);
10     y = find(y);
11     if(x != y) {
12         pre[y] = x;
13     }
14 }
15 inline void init() {
16     for(int i = 0; i < maxn; i++) {
17         pre[i] = i;
18     }
19 }

pre数组存放的是角标为序号的节点的父节点（初始化将所有节点的父节点设置为自己）。查询节点的父节点时可以递归地调用find函数，不断更新和查找父节点。直到自己是自己的父亲为止。并查集看起来很像一个森林。并的操作更简单了，只要看看两个元素的父节点是否相同，如果不相同那么任意合并一个到另一个树上即可。

　　回到kruskal算法，kruskal正是使用了这个精巧的数据结构维护了所有点的连通性。代码如下：

验题：poj2349

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 typedef struct Point {
23     int x;
24     int y;
25     double r;
26 }Point;
27 
28 bool cmp(Point x, Point y) {
29     return x.r < y.r;
30 }
31 
32 const int maxn = 222222;
33 priority_queue<int> pq;
34 int n, s, p;
35 int x[maxn],y[maxn];
36 double d[maxn];
37 int pre[maxn];
38 Point poi[maxn];
39 
40 void init() {
41     while(!pq.empty()) pq.pop();
42     for(int i = 0; i <= maxn; i++) {
43         pre[i] = i;
44     }
45 }
46 
47 int find(int x) {
48     return x == pre[x] ? x : pre[x] = find(pre[x]);
49 }
50 
51 bool unite(int x, int y) {
52     x = find(x);
53     y = find(y);
54     if(x != y) {
55         pre[x] = y;
56         return 1;
57     }
58     return 0;
59 }
60 
61 int main() {
62     // freopen("in", "r", stdin);
63     scanf("%d", &n);
64     while(n--) {
65         init();
66         scanf("%d %d", &s, &p);
67         for(int i = 0; i < p; i++) {
68             scanf("%d %d", &x[i], &y[i]);
69         }
70         int cnt = 0;
71         for(int i = 0; i < p; i++) {
72             for(int j = i+1; j < p; j++) {
73                 poi[cnt].x = i;
74                 poi[cnt].y = j;
75                 poi[cnt++].r = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
76             }
77         }
78         sort(poi, poi+cnt, cmp);
79         int cur = 0;
80         for(int i = 0; i < cnt; i++) {
81             if(unite(poi[i].x, poi[i].y)) {
82                 d[cur++] = poi[i].r;
83             }
84         }
85         printf("%.2f
", d[cur-s]);
86     }
87 }

kruskal

　　还有prim算法，与dijkstra算法非常相似，只是将dijkstra算法每次进行的松弛操作的d[j] = min(d[u]+G[u][j], d[j]);变成d[j] = min(G[u][j], d[j]);。每次贪心地选取从集合S到当前点的最小距离，之后将所有“集合到当前点的最小距离”相加即可。

 1 #pragma warning(disable:4996)
 2 
 3 
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <iomanip>
 7 #include <cstring>
 8 #include <climits>
 9 #include <complex>
10 #include <fstream>
11 #include <cassert>
12 #include <cstdio>
13 #include <bitset>
14 #include <vector>
15 #include <deque>
16 #include <queue>
17 #include <stack>
18 #include <ctime>
19 #include <set>
20 #include <map>
21 #include <cmath>
22 
23 using namespace std;
24 
25 const int maxn = 105;
26 const int inf = 0xffffff;
27 int d[maxn];
28 int G[maxn][maxn];
29 int vis[maxn];
30 int n, m;    //n:vertex m:edge
31 
32 void init() {
33     memset(vis, 0, sizeof(vis));
34     for(int i = 0; i <= n; i++) {
35         d[i] = inf;
36         for(int j = 0; j <= n; j++) {
37             G[i][j] = G[j][i] = inf;
38         }
39         G[i][i] = 0;
40     }
41 }
42 
43 int prim(int start) {
44     d[start] = 0;
45     for(int i = 1; i <= n; i++) {
46         int u = -1;
47         for(int j = 1; j <= n; j++) {
48             if(!vis[j]) {
49                 if(u == -1 || d[j] < d[u]) {
50                     u = j;
51                 }
52             }
53         }
54         vis[u] = 1;
55         for(int j = 1; j <= n; j++) {
56             if(!vis[j]) {
57                 d[j] = min(G[u][j], d[j]);
58             }
59         }
60     }
61     int sp = 0;
62     for(int i = 1; i <= n; i++) {
63         sp += d[i];
64     }
65     return sp;
66 }
67 
68 int main() {
69     // freopen("in", "r", stdin);
70     int u, v, w;
71     while(~scanf("%d %d", &m, &n) && m) {
72         init();
73         while(m--) {
74             scanf("%d %d %d", &u, &v, &w);
75             if(w < G[u][v]) {
76                 G[u][v] = G[v][u] = w;
77             }
78         }
79         int len = prim(1);
80         if(len > inf) puts("?");
81         else printf("%d
", len);
82     }
83 }

prim

　　同样地，也可以像dijkstra一样，使用堆优化。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 typedef pair<int, int> PII; //w v
23 
24 typedef struct E{
25     int w;
26     int v;
27     E() {}
28     E(int vv, int ww) : v(vv), w(ww) {}
29 }E;
30 
31 const int inf = 0x7fffff;
32 const int maxn = 111111;
33 int n, nn;
34 int vis[maxn], d[maxn];
35 vector<E> e[maxn];
36 priority_queue<PII, vector<PII>, greater<PII> > pq;
37 
38 int prim(int s) {
39     int mst = 0;
40     memset(vis, 0, sizeof(vis));
41     for(int i = 0; i <= n; i++) d[i] = inf;
42     while(!pq.empty()) pq.pop();
43     d[s] = 0;
44     pq.push(PII(0, 1));
45     while(!pq.empty()) {
46         PII cur = pq.top(); pq.pop();
47         int w = cur.first;
48         int v = cur.second;
49         if(vis[v] || d[v] < w) continue;
50         vis[v] = 1;
51         mst += w;
52         for(int i = 0; i < e[v].size(); i++) {
53             int u = e[v][i].v;
54             int w = e[v][i].w;
55             if(!vis[u] && w < d[u]) {
56                 d[u] = w;
57                 pq.push(PII(d[u], u));
58             }
59         }
60     }
61     return mst;
62 }
63 
64 int main() {
65     // freopen("in", "r", stdin);
66     int u, v, w;
67     while(~scanf("%d", &n) && n) {
68         nn = n * (n - 1) / 2;
69         for(int i = 0; i <= n; i++) e[i].clear();
70         for(int i = 0; i < nn; i++) {
71             scanf("%d %d %d", &u, &v, &w);
72             e[u].push_back(E(v, w));
73             e[v].push_back(E(u, w));
74         }
75         printf("%d
", prim(1));
76     }
77 }

prim+heap

验题：

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 const int maxn = 105;
23 const int inf = 0xffffff;
24 int d[maxn];
25 int G[maxn][maxn];
26 int vis[maxn];
27 int n, m;   //n:vertex m:edge
28 
29 void init() {
30     memset(vis, 0, sizeof(vis));
31     for(int i = 0; i <= n; i++) {
32         d[i] = inf;
33         for(int j = 0; j <= n; j++) {
34             G[i][j] = G[j][i] = inf;
35         }
36         G[i][i] = 0;
37     }
38 }
39 
40 int prim(int start) {
41     d[start] = 0;
42     for(int i = 1; i <= n; i++) {
43         int u = -1;
44         for(int j = 1; j <= n; j++) {
45             if(!vis[j]) {
46                 if(u == -1 || d[j] < d[u]) {
47                     u = j;
48                 }
49             }
50         }
51         vis[u] = 1;
52         for(int j = 1; j <= n; j++) {
53             if(!vis[j]) {
54                 d[j] = min(G[u][j], d[j]);
55             }
56         }
57     }
58     int sp = 0;
59     for(int i = 1; i <= n; i++) {
60         sp += d[i];
61     }
62     return sp;
63 }
64 
65 int main() {
66     // freopen("in", "r", stdin);
67     int u, v, w;
68     while(~scanf("%d %d", &n, &m) && n) {
69         init();
70         while(m--) {
71             scanf("%d %d %d", &u, &v, &w);
72             if(w < G[u][v]) {
73                 G[u][v] = G[v][u] = w;
74             }
75         }
76         printf("%d
", prim(1));
77     }
78 }

View Code

关于次小生成树，我们可以首先求出最小生成树，然后将最小生成树上的边依次取下。向上添加其他的边，这样就可以求得次小生成树了。可以看这一个题解：http://www.cnblogs.com/vincentX/p/4946099.html

转载请声明出处及作者，谢谢。