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;
}
测试: