最小生成树

这是图论中的一个问题，基本概念可以参照百度百科

http://baike.baidu.com/link?url=UT6VdWmNgZ6ZGJQwlTg3MuzUHBMlMIyYbQgfSDwY7V4kBoklD2oj-oReNVxXIr1OAlMxVLEls4wk82kRrN7dCq

最小生成树就是对于一个图来说，怎样花费最少把每个点都连通起来（不管直接还是间接），花费即可视为边的权。就是这样一个问题。

很显然，对于N个点的一个图（N阶图）来说，应该选N-1条边，少了连不通，多了浪费。所以关键就是怎么选这N-1条边的问题。

有两种算法来选边，prim算法和kruskal算法，前者是矩阵存储的图，后者是边集数组的图。实际上都是贪心算法。每次都选择一条最应该选择的边，重复N-1次。

　　先说说prim算法：

prim算法的基本思想是，标记数组s[n]用于表示第n个点目前是否可连通，从可连通的点与未连通的点所连接的边里选择一条最小的边，就是这次最该选择的边。选出这条边来之后更新s[n]，再次选边，直到选出N-1条边。

对于选出的边，存储下来就行啦。代码如下：

 1 #include<stdio.h>   //prim
 2 
 3 /*
 4   prim算法 
 5 */
 6 
 7 int main()
 8 {
 9     int a[20][20]={0},s[20]={0},i,j;
10     int n;
11     scanf("%d",&n);
12     for (i=1;i<=n;i++)
13       for (j=1;j<=n;j++)
14         scanf("%d",&a[i][j]);
15     int pre,rear,wei;
16     int k,min;
17     s[1]=1;  //初始时点1设为可连通，其他点都未连通
18     for (k=1;k<=n-1;k++)
19     {
20         min=10000;
21         for (i=1;i<=n;i++)
22           {
23               if (s[i])
24               {
25                   for (j=1;j<=n;j++)
26                   {
27                       if ((!s[j])&&(a[i][j]<min)&&(a[i][j]!=0))
28                       {
29                           pre=i;
30                           rear=j;
31                           wei=a[i][j];
32                           min=a[i][j];
33                       }
34                   }
35               }
36           }
37           s[rear]=1;  //更新新连通的一个点
38           printf("%d %d %d
",pre,rear,wei);
39     }
40     return 0;
41 }

下面再说kruskal算法：

这个算法直接省去了选最小边的过程，直接先把边排序（因为是按照边集数组存储的图），然后从小边开始逐个选，如果可以选，就选择，直到选出N-1条边。

那么问题来了，怎么知道这条边该不该选择呢？只需要判断如果选择了这条边是否会形成回路就可以啦。要是选了这条边会形成回路的话就肯定不选，如果没有形成回路的话肯定要选啊（因为这条边是目前最小的边啦）。

好，问题又来啦，怎么判断能不能形成回路呢？只需要把能连通的点放到同一个集合里，然后判断要加入的这条边连接的两个点是否在同一个集合里就行啦。

　　如果在同一个集合里，不能选择这条边；

　　如果不在同一个集合里，就选择这条边，并且更新集合，把两个点所在的集合合并。（具体实现方法可以参照代码）

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 typedef struct bian{
 5     int pre,rear,wei;
 6 }bian;
 7 
 8 int comp(void *a,void *b)
 9 {
10     int i=((bian *)a)->wei;
11     int j=((bian *)b)->wei;
12     return i-j;
13 }
14 
15 int jihe(int *x,int k)
16 {
17    if (x[k]==k) return k;
18    else return (jihe(x,x[k]));
19 }
20 
21 int main()
22 {
23     bian a[20];
24     int n,i,j,k,m,b[20];
25     scanf("%d%d",&n,&m);  //n是边的条数，m是点的个数 
26     for (i=1;i<=n;i++)
27       scanf("%d%d%d",&a[i].pre,&a[i].rear,&a[i].wei);
28     qsort(a+1,n,sizeof(bian),comp);
29     for (i=1;i<=m;i++)
30       b[i]=i;  //初始时，每个点都在各自的集合里 
31     int cou=0;
32     for (i=1;i<=n;i++)
33     {
34         if (jihe(b,a[i].pre)!=jihe(b,a[i].rear))
35         {
36             cou++;
37             printf("%d %d %d
",a[i].pre,a[i].rear,a[i].wei);
38             int mind=(a[i].pre>a[i].rear)?a[i].rear:a[i].pre;
39             int maxd=(a[i].pre<a[i].rear)?a[i].rear:a[i].pre;
40             b[maxd]=b[mind];  //把大的点加入小的点的集合，这样处理是为了防止边集数组输入时不按照小大的方式输入，造成递归混乱（个人认为是这样，可能也不会）
41         }
42         if (cou==n-1) break;
43     } 
44     return 0;
45 }

几天后我看了朋飞哥的博客（http://www.cnblogs.com/hxsyl/p/3286956.html）才知道原来我上面写的kruskal算法用到了并查集，哈哈，突然感觉自己好厉害~好吧，不过看了他的博客才知道这个还可以用路径压缩来优化。下面是路径压缩的代码（所谓路径压缩，就是直接把一个结点的父亲赋值成祖宗，就减少了递归次数）：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 typedef struct bian{
 5     int pre,rear,wei;
 6 }bian;
 7 
 8 int comp(void *a,void *b)
 9 {
10     int i=((bian *)a)->wei;
11     int j=((bian *)b)->wei;
12     return i-j;
13 }
14 
15 int jihe(int *x,int k)
16 {
17    if (x[k]==k) return k;
18    else return (jihe(x,x[k]));
19 }
20 
21 int main()
22 {
23     bian a[20];
24     int n,i,j,k,m,b[20];
25     scanf("%d%d",&n,&m);  //n是边的条数，m是点的个数 
26     for (i=1;i<=n;i++)
27       scanf("%d%d%d",&a[i].pre,&a[i].rear,&a[i].wei);
28     qsort(a+1,n,sizeof(bian),comp);
29     for (i=1;i<=m;i++)
30       b[i]=i;  //初始时，每个点都在各自的集合里 
31     int cou=0;
32     for (i=1;i<=n;i++)
33     {
34         int mind=(a[i].pre>a[i].rear)?a[i].rear:a[i].pre;
35         int maxd=(a[i].pre<a[i].rear)?a[i].rear:a[i].pre;        
36         int kk1=jihe(b,mind);
37         int kk2=jihe(b,maxd); 
38         if (kk1!=kk2)
39         {
40             cou++;
41             printf("%d %d %d
",a[i].pre,a[i].rear,a[i].wei);
42             b[maxd]=kk1;  //路径压缩 
43         }
44         if (cou==n-1) break;
45     } 
46     return 0;
47 }

过了一个学期之后再看自己写的代码实在感觉惭愧，当时只是了解了算法的大体思想，但是实际上并没有最优的实现算法，比如prim算法竟然写了一个n^3复杂度的代码，kruskal也没有用姿势优美的并查集。