最小生成树kruskal算法

最小生成树（最小权值生成树的简称）。

原理：每次选择一条最小权边，直至构成一棵最小生成树。

最小生成树的构建过程：

1.排序。将图中所有边的权值按从小到大的顺序排列成L：T<-NULL.

2.当|T|
  

   
a。选L中的最小权边e。

   
b。若TU{e}中不存在回路，将e加入T：T<-TU{e}。

   
c。从L中删除e：L<-L-{e}.

   
3.结束。

   
代码如下：

   

//并查集操作
int findfather(int i)
{
 if(root[i] == i)
   return root[i] ;
 else
  return findfather(root[i]);
}
void makeset(int i)
{
 root[i] = i;
 
 heavy[i] = 1 ;
}
void unio(int i , int j)
{
 
  if(heavy[i] >= heavy[j])
  {
    root[j] = i ;
    heavy[i] = heavy[i] + heavy[j] ; 
  }
  else 
  {
   root[i] = j ;
   heavy[j] = i ;
  }
}
typedef struct 
{
  int x , y , distance ;
  
}Edge ;





void kruskal()
{
 sort(g.begin() , g.end() , com) ;
 
 int shortlength = 0 ;
 
 int s , t ;
 
 for(int i = 0; i < n; i ++)
 {
   s = root[g[i].x] ;
   
   t = root[g[i].y] ;
   
   if(s != t)
   {
    shortlength = shortlength + g[i].distance ;
    unio(s , t) ;
   }
 }
}