数据结构与算法分析–Minimum Spanning Tree(最小生成树)

给定一个无向图,如果他的某个子图中,任意两个顶点都能互相连通并且是一棵树,那么这棵树就叫做生成树(spanning tree).
如果边上有权值,那么使得边权和最小的生成树叫做最小生成树(MST,Minimum Spanning Tree)。
 
 
 
1.prim版本的算法
 

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }

   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:  }

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }

2.Kruskal版本的算法

Kruskal算法按照边的权值从小到大排序,再全部访问一遍,如果将该边加入当前生成树内不会产生圈,那么就把这条边加入到生成树中,逐步扩大生成树的大小。

接下来我们介绍如何判断是否产生重边。假设现在要把连接顶点u和顶点v的边e(u—>v,v—>u)加入到生成树中去,如果加入操作之前,u和v不在同一个连通分量内(两块不连接的图),那么加入e也不会产生圈。反之,如果u和v在同一个连通分量里,那么一定会产生圈。可以使用并查集搞笑的判断是否属于同一个连通分量。

   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:  }

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }

上一篇:OpenCV 连接 Android IP摄像头


下一篇:html头部规范书写