最小生成树

Kruskal算法

伪代码：

T=(V,X）；

while（T中所含边数<n-1）

{      
        从E中选取当前权值最小的边(u,v);
       从E中删除边(u,v);
         if(边（u，v）的两个顶点落在两个不同的连通分量上）
            将边（u，v）并入T中；
}

并查集:

void UFset()                              //初始化
{
               for（int i=0;i<N;i++）
                       parent[i]=-1;
}

int Find(int x)
{

            int s;//查找位置
                        //一直查找到parent[s]为负数（此时的s即为根节点）为止
              for(s=x;parent[s]>=0;s=parent[s])
           while(s!=x)
          {
                   int tmp=parent[x];
                    parent[x]=s;
                  s=tmp;
           }
          return s;
}

void Union(int R1,int R2)
{
        //r1为R1的根节点，r2为R2的根节点
         int r1=Find(R1),r2=Find(R2);
         int tmp=parent[r1]+parent[r2];    //两个集合接点个数之后（负数）
        //如果R2所在树节点个数>R1树节点个数（parent[r1]和parent[r2]均为负数）
        if（parent[r1]>parent[r2]）
       {
              parent[r1]=r2;
             parent[r2]=tmp;
       }
       else
       {         
               parent[r2]=r1;
               parent[r1]=tmp;
      }
}