prim算法

// prim.cpp: 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#include<stdlib.h>
#include<stdio.h>
#define maxSize 100
#define INF 0xffff
typedef struct {
    double edges[maxSize][maxSize];
    int n, e;
    //VertexType vex[maxSize];
}MGraph;//图的邻接矩阵类型 
MGraph  init_graph(MGraph a) {
    printf("input num_of_vertex and num_of_edges :\n");
    scanf_s("%d%d", &a.n, &a.e);
    //printf("%d %d\n",a.n,a.e);
    int i, j, firstv, lastv;
    double value;
    for (i = 0; i<a.n; ++i) {
        for (j = 0; j<a.n; ++j) {
            a.edges[i][j] = INF;
            //printf("%f  ",a.edges[i][j]);
        }
        //printf("\n");
    }
    /*for(i=0;i<a.n;++i){
    //printf("第%d个顶点编号：\n",i+1);
    //scanf("%d",&a.vex[i].no);
    a.vex[i].no=i;
    } */
    //printf("%d %d\n",a.n,a.e);
    for (j = 0; j<a.e; ++j) {
        printf("输入第%d条边两端的顶点编号和顶点边的权值(顶点编号从0开始)：\n", j + 1);
        scanf_s("%d%d%lf", &firstv, &lastv, &value);
        //printf(":::\n%d",firstv);
        //printf(":::%f\n",value);
        a.edges[firstv][lastv] = value;
        //printf(":::%f",a.edges[firstv][lastv]);
        a.edges[lastv][firstv] = value;
    }
    return a;

}
void Prim(MGraph g, int first_v, double *sum) {
    double lowcost[maxSize], min;
    int vset[maxSize], v = 0;
    int i, j, k;
    for (i = 0; i<g.n; ++i) { //初始化 
        lowcost[i] = g.edges[first_v][i];
        vset[i] = 0;
    }
    //printf("g.n=%d\n",g.n);
    vset[first_v] = 1; //并入第一个顶点
    *sum = 0; //sum清零 
    for (i = 1; i<g.n; ++i) {
        min = INF;
        for (j = 1; j<g.n; ++j) {
            if (vset[j] == 0 && lowcost[j]<min) {
                min = lowcost[j];
                k = j;
            }
        }
        vset[k] = 1;
        printf("从%d到%d,权值为%f\n", v, k, min);
        v = k;
        *sum += min;

        for (j = 0; j<g.n; ++j) { //更新v顶点到各边的权值 
            if (vset[j] == 0 && g.edges[v][j]<lowcost[j])
                lowcost[j] = g.edges[v][j];
        }
    }

}
int main(int argc, char** argv) {
    double sum;
    MGraph G;
    G = init_graph(G);
    //printf("G.n=%d\nG.e=%d\nG.edges=%f",G.n,G.e,G.edges[0][1]);
    Prim(G, 0, &sum);
    printf("最小生成树的大小是：%f", sum);
    system("pause");
    return 0;
}

测试：