给定一个无向图，如果他的某个子图中，任意两个顶点都能互相连通并且是一棵树，那么这棵树就叫做生成树（spanning tree）.

如果边上有权值，那么使得边权和最小的生成树叫做最小生成树（MST，Minimum Spanning Tree）。

1.prim版本的算法

   1:  #include<string.h>

   2:  #define INF 10000001

   3:  #define N 10001

   4:  int graph[N][N];                     //夹着我们有N个点，这里存的是边（i，j）的花费（无向边）

   5:  //没有边时的花费就是INF

   6:  int cost[N];                         //记录目前要把第i个点加入正确联盟所需要的花费

   7:  int last[N];                         //记录第i个点是透过谁加入了正确联盟（等于是存在edge（last[i],i））

   8:  int choosed[N];                      //记录是否已经加入正确联盟

   9:  int fin_cnt;                         //记录已经加入正确联盟点的个数

  10:  int total_cost;                      //记录总花费

  11:  void init(){

  12:      int i;

  13:      memset( choosed , 0 , sizeof(int));

  14:      //last = -1代表自己就是root，一开始所有点都是自己的parent

  15:      memset( last , -1 , sizeof(int));

  16:   

  17:      //以idx=0的点作为root开始看花费

  18:      cost[0]=0;

  19:      choosed[0]=1;

  20:      for( i = 1 ; i < N ; i++ ){

  21:          cost[i] = graph[0][i];       //如果有边cost就会是该条边，反之则会是INF

  22:          if( cost[i] != INF)

  23:              last[i] = 0;

  24:      }

  25:      fin_cnt=1;                       //一开始只有一个点在正确联盟

  26:  }

  27:   

  28:  void prim(){            

  29:      int min;                         //用来存这一轮找到的最小花费

  30:      int min_idx;                     //用来存这一轮找到最小花费的是哪个点

  31:      int i;        

  32:      while( fin_cnt < N ){            //如果小于N代表还没找完

  33:          min = INF;                   //初始化成INF，用来找最小值

  34:          min_idx=-1;    

  35:          for( i = 1 ; i < N ; i++ ){  //跑过所有点，找最小值

  36:              if(choosed[i] == 0&&cost[i]<min){//已经在正确联盟里就不考虑

  37:                  min_idx=i;

  38:                  min=cost[i];

  39:              }

  40:          }

  41:          if( min_idx == -1 )          //如果没有找到就代表此图找不到spanning tree

  42:              break;   

  43:   

  44:          choosed[min_idx]=1;          //标记min_idx这个点进入了正确联盟

  45:          total_cost+=cost[min_idx];   //加上加入这个点的cost

  46:          fin_cnt++;                   //fin_cnt增加一，代表多了一个点已经确定

  47:   

  48:          //看看还有没有被选的点，有没有点能够透过min_idx这个点而更近的

  49:          for( i = 1 ; i < N ; i++){

  50:              if(choosed[min_idx] == 0 && graph[min_idx][i]<cost[i]){          //被选过的就跳过,有更近就更新

  51:                  last[i] = min_idx;

  52:                  cost[i] = graph[min_idx][i];

  53:              }

  54:          }

  55:      }

  56:  }

   1:  #include<stdlib.h>   //使用memset需要包含的头文件

   2:  #include<stdio.h>

   3:  #include<string.h>

   4:  #define maxn 10000

   5:  #define N 101

   6:  struct node{

   7:      int u,v,w;

   8:  }edges[maxn];

   9:  int total_cost;

  10:  int id[N];

  11:  int choosed[N];

  12:  int comp(const void*p,const void *q){//qsort需要重写它的排序规则

  13:      struct node a=*(struct node *)p;//类型强制转换

  14:      struct node b=*(struct node *)q;

  15:      return a.w-b.w;

  16:  }

  17:  int find_root(int idx){

  18:      if(id[idx]==-1)

  19:          return idx;

  20:      return id[idx]=find_root(id[idx]);

  21:  }

  22:   

  23:  void init(int n,int m){

  24:      int i;

  25:      memset(choosed,0,sizeof(choosed));

  26:      qsort(edges,n,sizeof(struct node),comp);//按边从小到大排序

  27:   

  28:      for(i=0;i<=m;i++)

  29:          id[i]=-1;

  30:      total_cost=0;

  31:  }

  32:  void kruskal(int n){

  33:      int i,x,y;

  34:      for(i=0;i<n;i++){

  35:          x=find_root(edges[i].u);

  36:          y=find_root(edges[i].v);

  37:          if(x!=y){//如果该条边添加后不构成回路

  38:              id[y]=x;

  39:              total_cost+=edges[i].w;//加上该条边的权重

  40:              choosed[edges[i].u]=1;

  41:              choosed[edges[i].v]=1;

  42:          }

  43:      }

  44:  }