最小生成树——普里姆算法(Prim)和克鲁斯卡尔算法(Kruskal)

墨蓝 2022-07-15 08:29 170阅读 0赞

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图联通的最少的边,n-1条边。

最小生成树即代价最小的生成树。【例】网络G表示n各城市之间的通信线路网线路（其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价）。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。

求解最小生成树的2种方法：

一、普里姆算法(Prim)

假设 WN=(V,\{E\}) 是一个含有 n 个顶点的连通网，TV 是 WN 上最小生成树中顶点的集合，TE 是最小生成树中边的集合。显然，在算法执行结束时，TV=V，而 TE 是 E 的一个子集。在算法开始执行时，TE 为空集，TV 中只有一个顶点，因此，按普里姆算法构造最小生成树的过程为：在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树上，直至生成树中含有 n-1条边为止。代码：

/* prim算法 */ /* ID: luyumia2 LANG: C TASK: agrinet */ 
    #include<stdio.h> 
    #include<math.h> 
    int main() 
    { 
        int n,i,j,k,m,minu,ans=0,a[105][105]; 
        char v[105];
        FILE *fin=fopen("agrinet.in","r"); 
        FILE *fout=fopen("agrinet.out","w"); 
        fscanf(fin,"%d",&n); 
        for(i=0;i<n;i++)
        { 
            for(j=0;j<n;j++) 
                fscanf(fin,"%d",&a[i][j]); 
            v[i]=0; 
        } 
        v[0]=1; 
        for(k=1;k<n;k++) 
        { 
            m=9999999; 
            for(i=0;i<n;i++) 
            { 
                if(v[i]==0) 
                { 
                    for(j=0;j<n;j++) 
                        if(v[j]==1) 
                            if(m>a[i][j]) 
                                { 
                                    m=a[i][j]; 
                                    minu=i; 
                                } 
                } 
            } 
            v[minu]=1; ans+=m; 
        } 
        fprintf(fout,"%d\n",ans);
        return 0; 
    }

二、克鲁斯卡尔算法(Kruskal）

开始全部是点集，没有边，依次选取代价最小的边，且不构成回路。可以用并查集，一开始每个点自己是一个集合，判断一条边时，如果发现他们在并查集中的祖先相同，则会构成回路，否则不会。把这条边加入时，只要把他们的祖先并起来就可以了。查找祖先的时候可以顺便压缩一下路径，每次均摊时间复杂度O(1)。