//用Prime算法解最小生成树,适用于稠密图,因为它需要建立二维的邻接矩阵表示点与点之间的关系,当然邻接表也是适用的
//Prime算法用两个集合表示,一个集合A表示已构成生成树的点,另一个集合B表示未加入该集合的点;而每一次的操作就是让集合B中与集合A距离最近的//点加入集合B(不是与集合A中所有点都最近,而是在所有点与点之间的距离最近)

#include <stdio.h>
#include <string.h>

#define INF 0x7fffffff
#define N 100

int map[N+5][N+5],clost[N+5];
char vis[N+5];
int n,sum;

void prim(int s){
    int i,j,k,min;
    vis[s]=1;//祖先自己先进入集合
    sum=0;
    for(i=1;i<=n;i++)
        clost[i]=map[s][i];//初值均为与祖先的差距
    for(i=1;i<n;i++){//n-1次即可
        min=INF;
        for(j=1;j<=n;j++)
            if(!vis[j] && clost[j]<min){
                min=clost[j];
                k=j;
            }//循环找到与最后加入集合点的最小距离
        sum+=min;
        vis[k]=1;//加入集合
        for(j=1;j<=n;j++)//更新与最后加入集合点的最小距离
            if(!vis[j] && k!=j && map[k][j]<clost[j]){
                clost[j]=map[k][j];
            }
    }
}
void init(){    
    int i,j;
    memset(vis,0,sizeof(vis));
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++)
            scanf(“%d”,&map[i][j]);
    }
}

int main(){
    while(scanf(“%d”,&n)!=EOF){
        init();
        prim(1);
        printf(“%d\n”,sum);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation