带权连通图的最小生成树——Kruskal算法的理解

    PRIM 和 KRUSKAL 的区别 
    1.  单位不同 Prim  以点为单位 以边为判定条件 找出  代价最小的点。 KRUSKAL 是以 边的为单位 ，以点为 判定条件找出可用的边
   2.  算法的数据结构不同， PRIM 针对的是 邻接矩阵  ，Kruskal  针对 是 边集数组

1. 把所有权值的边进行排序

2. 找出最小权值最小的边，记录此时连接的点

3. 继续寻找 下个权值最小的边，如果 此时形成的图没有环，此边就生效，并记录心新连接的点

4. 重复上述步骤 ，直到连接了所有的边

9fb316cd967dc54ff48dd62a2719aeb0.jpg

void MiniSpanTree_kursKal(MGraph G)
{

   int find(int * parent,int f);

   int  i,n,m,maxedges;
    maxedges= MAXVEX*(MAXVEX-1)/2;

    Edge edges[maxedges];
    int parent[MAXVEX];

    for(i=0;i<G.numVertexes;i++)
    {
         parent[i]=0;


    }

    for (i = 0; i <G.numEdeges ; ++i)
    {
         n= find(parent,edges[i].start);
         m=find(parent,edges[i].end);

        if(n!=m)
        {
             parent[n]=m;

        }

    }


    int  find(int * parent, int f)
    {
        while(parent[f]>0)
        {
            f=parent[f];
        }
        return  f;

    }


}