首页 > 编程语言 > 详细

最小生成树算法 1.Prim算法

时间:2018-05-25 21:01:35      阅读:249      评论:0      收藏:0      [点我收藏+]

最小生成树(MST):一个有N个点的图,边一定是大于等于N-1条边的。在这些边中选择N-1条出来,连接所有N个点。这N-1条边的边权之和是所有方案中最小的。

 

Prim算法的时间复杂度时O(n^2)的,因此适用于稠密图的最小生成树,如果是稀疏图的情况下采用Kruskal算法更好。

Prim算法蕴含了贪心的思想,其原理是把图中所有的点分成两个集合,一个集合(V)是已经在生成树中的点,另一个集合(G)是不在生成树中的点,然后寻找起点在V中,终点在G中的边中权值最小的边加入生成树,然后把终点从G移到V中,最后直到G中没有元素即可。这样做既保证了最小生成树的要求也不会产生回路。

code:

#include<stdio.h>
#include<stdlib.h>
#define max 10000000
int g[7][7]={{max,2,max,max,max,3,max},
                 {2,max,3,10,max,5,max},
                 {max,3,max,6,7,max,max},
                 {max,10,6,max,5,9,max},
                 {max,max,7,5,max,3,15},
                 {3,5,max,9,3,max,max},
                 {max,max,max,max,15,max,max}}; int i,dist[7],flag[7]={},j,s=0;
void prim(int vi){
   
    for(i=0;i<7;i++)
        dist[i]=g[vi][i];
    flag[vi]=1;
    for(i=0;i<6;i++){
        int min=max;
        int k;
        
        for(j=0;j<7;j++){
            if(dist[j]<min && !flag[j]){
                k=j;
                min=dist[j];
            }
        }
        flag[k]=1;
        for(j=0;j<7;j++){
            if(dist[j]>g[k][j])
             dist[j]=g[k][j];
        }
    }
}
int main(){
    int i,j;
    prim(1);
    for(i=1;i<7;i++) {
    s+=dist[i];
    printf("%d\n",dist[i]);}
    printf("%d",s);
    return 0;
}

 

最小生成树算法 1.Prim算法

原文:https://www.cnblogs.com/uncklesam7/p/9090364.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!