欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

prim算法

程序员文章站 2022-06-04 10:49:05
...
// 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;
}

测试:
prim算法