关于生成树

　　基本概念：

　　树：如果一个无向连通图G中不存在回路，则称图G是一颗树。

　　生成树：无向连通图G的一个子图如果是一颗包含了G中所有顶点的树，则称它为图G的生成树。

注意：生成树是图G的极小连通子图，表示在若在图中任添加一条边都将形成一个回路，同样的，若任意去掉一条边都将使图不在连通。

　　如果在边中加上权值，那么权值最小的生成树即为最小生成树，权值最大的生成树为最大生成树。

　　最小生成树算法：

　　由生成树的定义不难知道，BFS或DFS不重复的遍历结果就是一个生成树。通常情况下，我们都是要求最小生成树的。求最小生成树的算法有三种：Kruskal算法，Boruvka算法，Prime算法。常用的是Kruskal算法和Prime算法。

　　Kruskal算法核心思想：作用与边，每次选取当前可用的最小权值的边。

Kruskal算法有两个注意的地方：① 当前可用，即若某边的权值最小，但它关联的两个顶点本省已经在同一个集合里了也是不可选的。

　　　　　　　　　　　　　　 ② 最小权值，这个是必须的，不多说。

　　Prime算法核心思想：作用与顶点，通过选择当前可用的最小权值的边把其他顶点加入到生成树当中。

算法过程：

1.将一个图的顶点分为两部分，一部分是最小生成树中的结点（A集合），另一部分是未处理的结点（B集合）。

2.首先选择一个结点，将这个结点加入A中，然后，对集合A中的顶点遍历，找出A中顶点关联的边权值最小的那个B中的结点（设为v），将此顶点从B中删除，加入集合A中。

3.重复步骤2，直到B集合中的结点为空，结束此过程。

4.A集合中的结点就是由Prime算法得到的最小生成树的结点，依照步骤2的结点连接这些顶点，得到的就是这个图的最小生成树。

代码：

 1 int mat[N][N];
 2 int lowcost[N];
 3 int pre[N];
 4 int n, m;
 5 bool used[N];
 6 
 7 int Prime(int s)
 8 {
 9     for(int i=1; i<=n; i++)
10         lowcost[i] = mat[s][i], pre[i]=s;
11     used[s] = true;
12     lowcost[s] = 0;
13     int mst=0, cnt=0;
14     for(int i=1; i<n; i++)
15     {
16         int tmp=INF, k;
17         for(int j=1; j<=n; j++)
18             if(!used[j] && lowcost[j]<tmp)
19                 tmp = lowcost[k=j];
20         if(tmp==INF) break;
21         used[k] = true;
22         // 输出最小生成树中边
23         printf("%d %d %d
", k, pre[k], lowcost[k]);
24         mst += tmp;
25         if(++cnt ==n-1) break;
26         for(int j=1; j<=n; j++)
27             if(!used[j] && mat[k][j] < lowcost[j])
28                 lowcost[j] = mat[k][j], pre[j]=k;
29     }
30     return mst;
31 }

View Code

　　最大生成树：

　　从最小生成的求法中，我们知道，关键都是每次选取权值最小的，那么最大生成树算法只需每次在Kruskal和Prime中选取最大的即可。

　　还可以这样，记录边权的时候，每次乘一个-1，变为负权的图，然后用Prime求最小生成树，再把结果×-1，也可得到最大生成树的权值。

　　次小生成树算法：

　　次小生成树：所谓的次小生成树，是指在边集与某一最小生成树的边集不完全相同的其它生成树中值最小的那个。因此在数值上，最小生成树可能会等于次小生成树，这种情况也可以看做最小生成数。

　　思路：最直观的解法是，首先求出最小生成树，并且记录最小生成树中的边，然后再枚举删除最小生成树的边并同时求最小生成树。

以POJ1679为例，Kruskal求次小生成树代码如下：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define _Clr(x, y) memset(x, y, sizeof(x))
  5 #define INF 0x3f3f3f3f
  6 #define N 110
  7 using namespace std;
  8 
  9 struct Edge
 10 {
 11     int a, b;
 12     int c;
 13     bool operator < (const Edge &a) const
 14     {
 15         return c < a.c;
 16     }
 17 }edge[N*N];
 18 int bleg[N], n, m;
 19 int mst_edge[N];
 20 
 21 int find(int x)
 22 {
 23     int y = x;
 24     while(y != bleg[y])
 25         y = bleg[y];
 26     while(x != bleg[x])
 27     {
 28         int px = bleg[x];
 29         bleg[x] = y;
 30         x = px;
 31     }
 32     return y;
 33 }
 34 
 35 void Union(int a, int b)
 36 {
 37     int pa=find(a), pb=find(b);
 38     if(pa != pb)
 39         bleg[pa] = pb;
 40 }
 41 
 42 inline void Init()
 43 {
 44     for(int i=0; i<=n; i++)
 45         bleg[i] = i;
 46 }
 47 
 48 void Kruskal()
 49 {
 50     int mst_1=0;
 51     Init();
 52     _Clr(mst_edge, 0);
 53     sort(edge, edge+m);
 54     int k=0;
 55     for(int i=0; i<m && k<n-1; i++)
 56     {
 57         int a=find(edge[i].a);
 58         int b=find(edge[i].b);
 59         if(a != b)
 60         {
 61             mst_edge[k] = i;
 62             Union(a, b);
 63             mst_1 += edge[i].c;
 64             k++;
 65         }
 66     }
 67     // 枚举删除最小生成树中所有边求MST
 68     for(int i=0; i<n-1; i++)
 69     {
 70         int mst_2=0, k=0;
 71         Init();
 72         for(int j=0; j<m && k<n-1; j++)
 73         {
 74             if(mst_edge[i] == j) continue;
 75             int a=find(edge[j].a);
 76             int b=find(edge[j].b);
 77             if(a != b)
 78             {
 79                 Union(a, b);
 80                 mst_2 += edge[j].c;
 81                 k++;
 82             }
 83         }
 84         if(mst_1==mst_2 && k==n-1)
 85         {
 86             puts("Not Unique!");
 87             return;
 88         }
 89     }
 90     printf("%d
", mst_1);
 91 }
 92 
 93 int main()
 94 {
 95     int T;
 96     scanf("%d", &T);
 97     while(T--)
 98     {
 99         scanf("%d%d", &n, &m);
100         for(int i=0; i<m; i++)
101             scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].c);
102         Kruskal();
103     }
104     return 0;
105 }

View Code