最小生成树问题——Prim算法（C实现）

问题介绍及算法思想参考
求最小生成树-普里姆算法
最小生成树Prim算法理解

代码实现

#include<stdio.h>
#include <stdlib.h>

#define MAX 100
#define Maxcost 0x7fffffff

int graph[MAX][MAX];

void prim(int graph[][MAX],int n){
    int i,j,k;
    int lowcost[MAX];
    int closeset[MAX],used[MAX];
    int mmin;
    int sumcost=0;
    printf("最小生成树的边为:\n");
    for(i=1;i<=n;i++){
        lowcost[i]=graph[1][i];
        //printf("lowcost[%d]=%d\n",i,lowcost[i]);
        closeset[i]=1;
        used[i]=0;
    }
    used[1]=1;
    for(i=2;i<=n;i++){
        j=1;
        mmin=Maxcost;
        for(k=2;k<=n;k++){
            if((!used[k])&&(lowcost[k]<mmin)){
                mmin=lowcost[k];
                j=k;
            }
        }
        printf("%d %d\n",j,closeset[j]);
        sumcost+=graph[j][closeset[j]];
        used[j]=1;
        for(k=2;k<=n;k++){
            if(!used[k]&&(graph[j][k]<lowcost[k])){
                lowcost[k]=graph[j][k];
                closeset[k]=j;
            }
            //printf("lowcost[%d]=%d\n",k,lowcost[k]);
        }
    }
    printf("最小造价为：%d\n",sumcost);
}

int main(){
    FILE *fr;
    int s,e;
    int i,j,weight;
    fr=fopen("input.txt","r");
    if(!fr){
        printf("openning file failed!\n");
        exit(1);
    }
    fscanf(fr,"%d %d",&s,&e);
    printf("共%d个点 %d条边\n",s,e);
    for(i=0; i<=e; i++)
    for(j=0; j<=e; j++)
        graph[i][j] = Maxcost;
    while(e--){
        fscanf(fr,"%d%d%d",&i,&j,&weight);
        printf("%d %d %d\n",i,j,weight);
        graph[i][j]=weight;
        graph[j][i]=weight;
    }
    prim(graph,s);
    return 0;
}

input

 6 10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6

output