考考你这普里姆算法错在哪？

隨鈊乄鎍慾

直入正题上代码：#include<stdio.h>
#define MaxVertexNum 20
#define INF 32767
typedef struct
{
       int vexs[MaxVertexNum];
       int AdjMatrix[MaxVertexNum][MaxVertexNum];
       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[i][j]=INF;
       printf("输入%d条边,格式：行下标 列下标边上的权值<CR>\n",G.arcnum);
       for(k=0;k<G.arcnum;k++)
       {
                scanf("%d %d %d",&i,&j,&x);G.AdjMatrix[i][j]=x;
                G.AdjMatrix[j][i]=G.AdjMatrix[i][j];
       }
}
void Prim(MGraph &G)
{
       int n=G.vexnum;
       int lowerCost[MaxVertexNum],mincost=0,closeVertex[MaxVertexNum];
       TreeEdge close[MaxVertexNum];
       int i,j,k,sum=0;
       for(i=1;i<n;i++)
       {lowerCost[i]=G.AdjMatrix[0][i];closeVertex[i]=0;}
       lowerCost[0]=0;
       closeVertex[0]=0;
       for(i=1;i<n;i++)
       {
                mincost=INF;
                j=1;k=1;
                while(j<n)
                {
                          if(lowerCost[j]!=0&&lowerCost[j]<mincost)
                          {mincost=lowerCost[j];k=j;}
                          j++;
                }
                close[i-1].begin=closeVertex[k];close[i-1].end=k;close[i-1].cost=mincost;
                sum=sum+mincost;
                lowerCost[k]=0;
                for(j=1;j<n;j++)
                          if(G.AdjMatrix[k][j]<lowerCost[j])
                          {lowerCost[j]=G.AdjMatrix[k][j];closeVertex[j]=k;}
       }
       printf("最小生成树如下所示：\n始点  终点  权值\n");
       for(i=0;i<n-1;i++)
       {printf("%d %d %d\n",close[i].begin,close[i].end,close.cost);}
       printf("最小生成树的总权和为%d\n",sum);
}
void main()
{
       MGraph G;
       CreatMGraph1(G);
       Prim(G);
}

[/i][/i][/i][/i][/i][/i][/i][/i][/i]

xubo

:sweat: