最小生成树算法

最小生成树算法是给定一个无向图，及其顶点和边的权值，在确保所有顶点都是连通即整个无向图的连通分量为1的情况下使得所有边的权值之和最小的算法，这个时候其实图已经退化为树了。

下面介绍一下最小生成树的两种算法：kruskal算法和prim算法。它们都属于贪心算法，只是贪心的理解角度不同导致的两种算法。对于最小生成树，最简单的最优度量准则是：选择迄今为止已入选S中边的代价之和增量最小的边。（其中S代表已经入选最小生成树集合的边）

一）kruskal算法：

贪心准则：按边的权值非降序考察E中的边，从中选择一条代价最小的边。这种做法使得算法在构造生成树的过程中，边集S代表的子图不一定是连通的，而且为了确保最终得到一棵生成树，每选择一条边时都需要判断SUe是否包含回路。时间复杂度为0(eloge)，其中e为图中边的个数，需要结合并查集解决。适合在稀疏图中。

二）prime算法：

贪心准则为：在保证S所代表的子图是一棵树的前提下选择一条最小代价边e=(u,v)。由于其选边方式已经确保S所代表的子图自然是一棵树。故无需判断边集SUe是否包含回路。

时间复杂度为O(n*n)，适合在n比较小的情况下。

两种算法的实现分别如下：

prim算法的思想是加点法。即开始时任意从图中选择一个点，作为U集合，其余点为S-U集合，其中S为原图中的顶点集合，求U集合中顶点到S-U集合中顶点的最小距离，这个最小距离即为最小生成树的组成边，然后将对应最小距离的S-U集合的顶点放入U集合，然后重复执行上述操作，直至U集合=S集合。

而kruskal算法则是加边法，即将图的边先从小到大排序，然后结合并查集依次加边，注意不能形成环，这也是并查集的作用，每次成功加入的边即为最小生成树的组成边。下面是代码：

//图的邻接矩阵表示法 #include 
  
    #include 
   
     #define Max 100 #define Inf 0x1111 typedef char type; typedef struct Grap{ type data[Max]; int value[Max][Max]; int n,m; }Grap,*pgrap; struct Adjtrim{ int index; int dis; }trim[Max]; int Located(pgrap g,char ch){ for(int i=0;i 
    
      n;i++) if(g->data[i]==ch) return i; } void Creat_grap(pgrap g){ printf("输入图的顶点数和边数:\n"); scanf("%d%d",&g->n,&g->m); //printf("ksgfdkj\n"); getchar(); printf("输入图中的顶点:\n"); int i,j; for(i=0;i 
     
       n;i++){ g->data[i]=getchar(); getchar(); } for(i=0;i 
      
        n;i++) for(j=0;j 
       
         n;j++) g->value[i][j]=Inf; printf("请输入图中的边:\n"); int index1,index2,value; char ch1,ch2; while(g->m--){ scanf("%c,%c,%d",&ch1,&ch2,&value); getchar(); index1=Located(g,ch1); index2=Located(g,ch2); g->value[index1][index2]=value; //无向图 //g->value[index2][index1]=value; } } /*void Show_grap(pgrap g){ printf("邻接矩阵表示法个顶点的邻接顶点:\n"); int i,j; for(i=0;i 
        
          n;i++){ printf("%c:",g->data[i]); for(j=0;j 
         
           n;j++) if(g->value[i][j]!=Inf) putchar(g->data[j]); printf("\n"); } }*/ int Minsearch(pgrap g){ int Minn=Inf; int index; for(int i=0;i 
          
            n;i++){ if(trim[i].dis!=0 && trim[i].dis 
           
             n;i++) if(i!=index){ trim[i].index=index; trim[i].dis=g->value[index][i]; } trim[index].dis=0; int s; int count=0; for(i=0;i 
            
              n-1;i++){ s=Minsearch(g); count+=trim[s].dis; printf("%c,%c,%d\n",g->data[s],g->data[trim[s].index],trim[s].dis); trim[s].dis=0; for(j=0;j 
             
               n;j++) if(trim[j].dis!=0 && g->value[s][j] 
              
                value[s][j]; } } printf("最小生成树的权值为：%d\n",count); } int main(){ Grap g; pgrap p=&g; Creat_grap(p); //Show_grap(p); printf("\n"); MinTreePrim(p,'A'); return 0; } 
               
              
             
            
           
          
         
        
       
      
     
    
  

测试数据：

下面是kruskal算法代码：

//最小生成树kruskal算法 #include 
   
     #include 
    
      #include 
     
       #define Max(a,b) a>b?(a):(b) #define Min(a,b) a 
      
        value-((Arcnode*)q)->value; } int find(int x){ int a=x,j; while(set[x]!=x) x=set[x]; j=a; while(j!=x){ a=set[j]; set[j]=x; j=a; } return x; } int main(){ printf("请输入图的顶点数和边数:\n"); scanf("%d%d",&n,&m); int i,x,y; for(i=0;i 
        
       
      
     
   

测试数据：

kruskal算法如下：288K+16MS

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define Maxx(a,b) (a>b)?(a):(b) #define Min(a,b) (a 
        
       
      
     
   

#include 
   
     #include 
    
      #include 
     
       #define Max 110 #define Inf int dis[Max]; int trim[Max][Max]; bool flag[Max]; int n; int find_min(){ int max_int=Inf,index; for(int i=1;i<=n;i++) if(!flag[i] && dis[i]