[转载]最小生成树-Prim算法和Kruskal算法

#define MAX  100000
#define VNUM  10+1                                             //这里没有ID为0的点,so id号范围1~10

int edge[VNUM][VNUM]={/*输入的邻接矩阵*/};
int lowcost[VNUM]={0};                                         //记录Vnew中每个点到V中邻接点的最短边

int addvnew[VNUM];                                             //标记某点是否加入Vnew

int adjecent[VNUM]={0};                                        //记录V中与Vnew最邻近的点

void prim(int start)
{
     int sumweight=0;
     int i,j,k=0;

     for(i=1;i<VNUM;i++)                                      //顶点是从1开始
     {
        lowcost[i]=edge[start][i];
        addvnew[i]=-1;                                         //将所有点至于Vnew之外,V之内，这里只要对应的为-1，就表示在Vnew之外

     }

     addvnew[start]=0;                                        //将起始点start加入Vnew

     adjecent[start]=start;
                                                 
     for(i=1;i<VNUM-1;i++)                                        
     {
        int min=MAX;
        int v=-1;
        for(j=1;j<VNUM;j++)                                      
        {
            if(addvnew[j]!=-1&&lowcost[j]<min)                 //在Vnew之外寻找最短路径

            {
                min=lowcost[j];
                v=j;
            }
        }
        if(v!=-1)
        {
            printf("%d %d %d
",adjecent[v],v,lowcost[v]);
            addvnew[v]=0;                                      //将v加Vnew中

            sumweight+=lowcost[v];                             //计算路径长度之和
            for(j=1;j<VNUM;j++)
            {
                if(addvnew[j]==-1&&edge[v][j]<lowcost[j])      
                {
                    lowcost[j]=edge[v][j];                     //此时v点加入Vnew需要更新lowcost

                    adjecent[j]=v;                             
                }
            }
        }
    }
    printf("the minmum weight is %d",sumweight);
}

对图的顶点数n做归纳，证明Kruskal算法对任意n阶图适用。

归纳基础：

n=1，显然能够找到最小生成树。

归纳过程：

假设Kruskal算法对n≤k阶图适用，那么，在k+1阶图G中，我们把最短边的两个端点a和b做一个合并操作，即把u与v合为一个点v'，把原来接在u和v的边都接到v'上去，这样就能够得到一个k阶图G'(u,v的合并是k+1少一条边)，G'最小生成树T'可以用Kruskal算法得到。

我们证明T'+{<u,v>}是G的最小生成树。

用反证法，如果T'+{<u,v>}不是最小生成树，最小生成树是T，即W(T)<W(T'+{<u,v>})。显然T应该包含<u,v>，否则，可以用<u,v>加入到T中，形成一个环，删除环上原有的任意一条边，形成一棵更小权值的生成树。而T-{<u,v>}，是G'的生成树。所以W(T-{<u,v>})<=W(T')，也就是W(T)<=W(T')+W(<u,v>)=W(T'+{<u,v>})，产生了矛盾。于是假设不成立，T'+{<u,v>}是G的最小生成树，Kruskal算法对k+1阶图也适用。

由数学归纳法，Kruskal算法得证。

typedef struct          
{        
    char vertex[VertexNum];                                //顶点表         
    int edges[VertexNum][VertexNum];                       //邻接矩阵,可看做边表         
    int n,e;                                               //图中当前的顶点数和边数         
}MGraph; 
 
typedef struct node  
{  
    int u;                                                 //边的起始顶点   
    int v;                                                 //边的终止顶点   
    int w;                                                 //边的权值   
}Edge; 

void kruskal(MGraph G)  
{  
    int i,j,u1,v1,sn1,sn2,k;  
    int vset[VertexNum];                                    //辅助数组，判定两个顶点是否连通   
    Edge E[EdgeNum];                                         //存放所有的边   
    k=0;                                                    //E数组的下标从0开始   
    for (i=0;i<G.n;i++)  
    {  
        for (j=0;j<G.n;j++)  
        {  
            if (G.edges[i][j]!=0 && G.edges[i][j]!=INF)  
            {  
                E[k].u=i;  
                E[k].v=j;  
                E[k].w=G.edges[i][j];  
                k++;  
            }  
        }  
    }     
    heapsort(E,k,sizeof(E[0]));                            //堆排序，按权值从小到大排列       
    for (i=0;i<G.n;i++)                                    //初始化辅助数组   
    {  
        vset[i]=i;  
    }  
    k=1;                                                   //生成的边数，最后要刚好为总边数   
    j=0;                                                   //E中的下标   
    while (k<G.n)  
    {   
        sn1=vset[E[j].u];  
        sn2=vset[E[j].v];                                  //得到两顶点属于的集合编号   
        if (sn1!=sn2)                                      //不在同一集合编号内的话，把边加入最小生成树   
        {
            printf("%d ---> %d, %d",E[j].u,E[j].v,E[j].w);       
            k++;  
            for (i=0;i<G.n;i++)  
            {  
                if (vset[i]==sn2)  
                {  
                    vset[i]=sn1;  
                }  
            }             
        }  
        j++;  
    }  
}