最小二叉树prim算法不知道哪里出错?
#include <stdio.h>
#include <stdlib.h>
#define mvnum 30//最多顶点
#define maxlent 50 //无穷 //
#define true 1
#define false 0
typedef struct AMGragh
{
char vexs[mvnum];//顶点数组
int arc[mvnum][mvnum];//边信息
int vexnum,arcnum;//顶点数和边数
}AMGraph;
struct closedge
{
char adjbex;//最小边在u中的顶点
int lowcost;//最小边权值
}closedge[mvnum];
int Locatevex(AMGraph *G,char temp)
{
for(int i=0;i<G->vexnum;i++)
{
if(G->vexs[i]==temp)
{
return i;
}
}
}
int CreateUDN(AMGraph *G)//图的生成函数
{
printf("请输入顶点数和边数:\n");
scanf("%d\t%d",&(G->vexnum),&(G->arcnum)); //输入边数
for(int i=0;i<G->vexnum;i++)//输入顶点
{
printf("请输入顶点%d\n",i+1);
scanf("%*c%c",&(G->vexs[i]));
printf("\n") ;
}
for(int j=0;j<(G->arcnum);j++)//初始化邻接矩阵
{
for(int i=0;i<(G->arcnum);i++)
G->arc[i][j]=maxlent;
}
for(int k=0;k<(G->arcnum);k++)//构造邻接矩阵
{
char v1,v2;
int i,j,w;
printf("请输入顶点v1,v2\n\t权值\n");
scanf("%*c%c%c%d",&v1,&v2,&w);
i=Locatevex(G,v1);
j=Locatevex(G,v2);
G->arc[i][j]=w;
G->arc[j][i]=w;
}
return 0;
}
int Print(AMGraph *G)
{
for(int i=0;i<G->vexnum;i++)
{
for(int j=0;j<G->vexnum;j++)
{
if(G->arc[i][j]<maxlent)
{
printf(" %-d",G->arc[i][j]);
if(j==2)
{
printf("\n");
}
}
else
{
printf(" %-d",maxlent);
if(j==2)
{
printf("\n");
}
}
}
}
}
int visited[mvnum];
void DFS(AMGraph *G,int i)
{
int j;
printf("%c",G->vexs[i]);
visited[i]=1;
for(j=0;j<G->vexnum;j++)
{
if(G->arc[i][j]==1&&visited[j]==0)
{
DFS(G,j);
}
}
}
void DFS_AM(AMGraph *G)
{
int i;
//初始化"标志"数组为0,代表未访问
for(i=0;i<G->vexnum;i++)
{
visited[i]=0;
}
for(i=0;i<G->vexnum;i++)
{
if(visited[i]==0)
{
DFS(G,i);//此处的G已经是指针类型,不需要再&G
}
}
}
int Min( closedge , AMGragh G)
{
int min = maxlent;
int index = 0;
for (int i = 0; i < G.vexnum; i++)
{
if (closedge[i].lowcost<min && closedge[i].lowcost != 0) //权值为0的表示已经加入点集合,所以不再遍历
{
min = closedge[i].lowcost;
index = i;
}
}
return index;
}
void MinispanTree_prim(AMGragh G,char u)
{
int k=Locatevex(G,u);
for(int j=0;j<G.vexnum;++j)
{
if(j!=k)
closedge[j]={u,arc[k][j]};
}
closedge[k].lowcost=0;
for(int i=0;i<G.vexnum;i++)
{
k=Min(closedge[mvnum],G);
char u0=closedge[k].adjbex;
char v0=G.vexs[k];
printf("%*c%c%c",u0,v0);
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;j++)
{
if(G.arc[k][j]<closedge[j].lowcost)
closedge[j]={G.vexs[k],G.arc[k][j]};
}
}
}
int main()
{
AMGraph G;
printf("建立无向网\n");
CreateUDN(&G);
printf("输出矩阵G:[][]\n");
Print(&G);
printf("\n深度优先遍历\n");
DFS_AM(&G);
printf("prim算法构建最小生成树\n");
printf("请输入起始顶点v");
int u;
scanf("%c",&u);
MinispanTree_prim(G,u);
return 0;
}
回复
1个回答

test
2024-07-04
void MinispanTree_prim(AMGraph G, char u)
{
int k = Locatevex(&G, u);
for (int j = 0; j < G.vexnum; ++j)
{
if (j != k)
{
closedge[j].adjbex = u;
closedge[j].lowcost = G.arc[k][j];
}
}
closedge[k].lowcost = 0;
for (int i = 0; i < G.vexnum; i++)
{
k = Min(closedge, G);
char u0 = closedge[k].adjbex;
char v0 = G.vexs[k];
printf("%c-%c\n", u0, v0);
closedge[k].lowcost = 0;
for (int j = 0; j < G.vexnum; j++)
{
if (G.arc[k][j] < closedge[j].lowcost)
{
closedge[j].adjbex = G.vexs[k];
closedge[j].lowcost = G.arc[k][j];
}
}
}
}
回复

适合作为回答的
- 经过验证的有效解决办法
- 自己的经验指引,对解决问题有帮助
- 遵循 Markdown 语法排版,代码语义正确
不该作为回答的
- 询问内容细节或回复楼层
- 与题目无关的内容
- “赞”“顶”“同问”“看手册”“解决了没”等毫无意义的内容