考考你这普里姆算法错在哪？
直入正题上代码：#include<stdio.h>#define MaxVertexNum 20
#define INF 32767
typedef struct
{
int vexs;
int AdjMatrix;
int vexnum,arcnum;
}MGraph;
typedef struct
{
int begin,end;
int cost;
}TreeEdge;
void CreatMGraph1(MGraph &G)
{
int i,j,k,x;
printf("请输入顶点数和边数（输入格式为：顶点数 边数）:\n");
scanf("%d %d",&(G.vexnum),&(G.arcnum));
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.AdjMatrix=INF;
printf("输入%d条边,格式：行下标 列下标边上的权值<CR>\n",G.arcnum);
for(k=0;k<G.arcnum;k++)
{
scanf("%d %d %d",&i,&j,&x);G.AdjMatrix=x;
G.AdjMatrix=G.AdjMatrix;
}
}
void Prim(MGraph &G)
{
int n=G.vexnum;
int lowerCost,mincost=0,closeVertex;
TreeEdge close;
int i,j,k,sum=0;
for(i=1;i<n;i++)
{lowerCost=G.AdjMatrix;closeVertex=0;}
lowerCost=0;
closeVertex=0;
for(i=1;i<n;i++)
{
mincost=INF;
j=1;k=1;
while(j<n)
{
if(lowerCost!=0&&lowerCost<mincost)
{mincost=lowerCost;k=j;}
j++;
}
close.begin=closeVertex;close.end=k;close.cost=mincost;
sum=sum+mincost;
lowerCost=0;
for(j=1;j<n;j++)
if(G.AdjMatrix<lowerCost)
{lowerCost=G.AdjMatrix;closeVertex=k;}
}
printf("最小生成树如下所示：\n始点终点权值\n");
for(i=0;i<n-1;i++)
{printf("%d %d %d\n",close.begin,close.end,close.cost);}
printf("最小生成树的总权和为%d\n",sum);
}
void main()
{
MGraph G;
CreatMGraph1(G);
Prim(G);
}
:sweat:
页:
[1]