数据结构的prim算法,图已经建好了,算法我找不出来哪里错了

时间:2022-10-08 19:22:45
#include<stdlib.h>
#include<stdio.h>
#define maxnum 20
typedef struct ArcCell
{
int adj;
}ArcCell,Adj[maxnum][maxnum];
typedef struct
{
char vexs[maxnum];
Adj arcs;
int vexnum,arcnum;
}Graph;
int locate(Graph G,char v)
{
for(int i=0;i<G.vexnum;i++)
if(v==G.vexs[i])
return i;
}
Graph creatgraph(Graph G)
{
int i,j,w,k;
char v,u;
printf("请输入顶点数和边数\n"); 
scanf("%d%d",&G.vexnum,&G.arcnum);
fflush(stdin);
printf("请输入顶点\n");
for(i=0;i<G.vexnum;i++){
printf("请输入第%d个顶点",i+1); 
scanf("%c",&G.vexs[i]);
fflush(stdin);
}
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
G.arcs[i][j].adj=32767;
}
for(k=0;k<G.arcnum;k++){
printf("请输入第%d对值\n",k+1);
scanf("%c%c%d",&v,&u,&w);
i=locate(G,v);
j=locate(G,u);
G.arcs[i][j].adj=w;
fflush(stdin);}
}
Graph primtree(Graph G)
{
int i,j,k;
struct{
char adjvex;
int lowcost;
}closedge[20];
k=3;
for(j=0;j<G.vexnum;j++)
if(j!=k)
closedge[j]={G.vexs[k],G.arcs[k][j].adj};
closedge[k].lowcost=0;
for(i=1;i<G.vexnum;i++) 
{
for(j=0;j<G.vexnum;j++)
{
if(closedge[j].lowcost>0)
k=j;
break;
}
for(j=0;j<G.vexnum;j++)
{
if(closedge[j].lowcost>0)
if(closedge[j].lowcost<closedge[k].lowcost)
k=j;
}
printf("%c %c",closedge[k].adjvex,G.vexs[k]);
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[k][j].adj<closedge[j].lowcost)
closedge[j]={G.vexs[k],G.arcs[k][j].adj};
}
}
return G;
}
int main()
{
Graph G;
creatgraph(G);
primtree(G);
}

2 个解决方案

#1


#include<stdlib.h> 

#include<stdio.h>
#define maxnum 20
typedef struct ArcCell
{
int adj;
}ArcCell,Adj[maxnum][maxnum];
typedef struct
{
char vexs[maxnum];
Adj arcs;
int vexnum,arcnum;
}Graph;
int locate(Graph G,char v)
{
for(int i=0;i<G.vexnum;i++)
if(v==G.vexs[i])
return i;
}
Graph creatgraph(Graph G)
{
int i,j,w,k;
char v,u;
printf("请输入顶点数和边数\n"); 
scanf("%d%d",&G.vexnum,&G.arcnum);
fflush(stdin);
printf("请输入顶点\n");
for(i=0;i<G.vexnum;i++){
printf("请输入第%d个顶点",i+1); 
scanf("%c",&G.vexs[i]);
fflush(stdin);
}
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
G.arcs[i][j].adj=32767;
}
for(k=0;k<G.arcnum;k++){
printf("请输入第%d对值\n",k+1);
scanf("%c%c%d",&v,&u,&w);
i=locate(G,v);
j=locate(G,u);
G.arcs[i][j].adj=w;
fflush(stdin);}
}
Graph primtree(Graph G)
{
int i,j,k;
struct{
char adjvex;
int lowcost;
}closedge[20];
k=3;
for(j=0;j<G.vexnum;j++)
if(j!=k)
closedge[j]={G.vexs[k],G.arcs[k][j].adj};
closedge[k].lowcost=0;
for(i=1;i<G.vexnum;i++) 
{
for(j=0;j<G.vexnum;j++)
{
if(closedge[j].lowcost>0)
k=j;
break;
}
for(j=0;j<G.vexnum;j++)
{
if(closedge[j].lowcost>0)
if(closedge[j].lowcost<closedge[k].lowcost)
k=j;
}
printf("%c %c",closedge[k].adjvex,G.vexs[k]);
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[k][j].adj<closedge[j].lowcost)
closedge[j]={G.vexs[k],G.arcs[k][j].adj};
}
}
return G;
}
int main()
{
Graph G;
creatgraph(G);
primtree(G);
}

#2


#include<stdlib.h>
#include<stdio.h>
#define maxnum 20
typedef struct ArcCell
{
int adj;
}ArcCell,Adj[maxnum][maxnum];
typedef struct
{
char vexs[maxnum];
Adj arcs;
int vexnum,arcnum;
}Graph;
int locate(Graph G,char v)
{
for(int i=0;i<G.vexnum;i++)
if(v==G.vexs[i])
return i;
}
Graph creatgraph(Graph G)
{
int i,j,w,k;
char v,u;
printf("请输入顶点数和边数\n"); 
scanf("%d%d",&G.vexnum,&G.arcnum);
fflush(stdin);
printf("请输入顶点\n");
for(i=0;i<G.vexnum;i++){
printf("请输入第%d个顶点",i+1); 
scanf("%c",&G.vexs[i]);
fflush(stdin);
}
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
G.arcs[i][j].adj=32767;
}
for(k=0;k<G.arcnum;k++){
printf("请输入第%d对值\n",k+1);
scanf("%c%c%d",&v,&u,&w);
i=locate(G,v);
j=locate(G,u);
G.arcs[i][j].adj=w;
fflush(stdin);}
}
Graph primtree(Graph G)
{
int i,j,k;
struct{
char adjvex;
int lowcost;
}closedge[20];
k=3;
for(j=0;j<G.vexnum;j++)
if(j!=k)
closedge[j]={G.vexs[k],G.arcs[k][j].adj};
closedge[k].lowcost=0;
for(i=1;i<G.vexnum;i++) 
{
for(j=0;j<G.vexnum;j++)
{
if(closedge[j].lowcost>0)
k=j;
break;
}
for(j=0;j<G.vexnum;j++)
{
if(closedge[j].lowcost>0)
if(closedge[j].lowcost<closedge[k].lowcost)
k=j;
}
printf("%c %c",closedge[k].adjvex,G.vexs[k]);
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[k][j].adj<closedge[j].lowcost)
closedge[j]={G.vexs[k],G.arcs[k][j].adj};
}
}
return G;
}
int main()
{
Graph G;
creatgraph(G);
primtree(G);
}

#1


#include<stdlib.h> 

#include<stdio.h>
#define maxnum 20
typedef struct ArcCell
{
int adj;
}ArcCell,Adj[maxnum][maxnum];
typedef struct
{
char vexs[maxnum];
Adj arcs;
int vexnum,arcnum;
}Graph;
int locate(Graph G,char v)
{
for(int i=0;i<G.vexnum;i++)
if(v==G.vexs[i])
return i;
}
Graph creatgraph(Graph G)
{
int i,j,w,k;
char v,u;
printf("请输入顶点数和边数\n"); 
scanf("%d%d",&G.vexnum,&G.arcnum);
fflush(stdin);
printf("请输入顶点\n");
for(i=0;i<G.vexnum;i++){
printf("请输入第%d个顶点",i+1); 
scanf("%c",&G.vexs[i]);
fflush(stdin);
}
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
G.arcs[i][j].adj=32767;
}
for(k=0;k<G.arcnum;k++){
printf("请输入第%d对值\n",k+1);
scanf("%c%c%d",&v,&u,&w);
i=locate(G,v);
j=locate(G,u);
G.arcs[i][j].adj=w;
fflush(stdin);}
}
Graph primtree(Graph G)
{
int i,j,k;
struct{
char adjvex;
int lowcost;
}closedge[20];
k=3;
for(j=0;j<G.vexnum;j++)
if(j!=k)
closedge[j]={G.vexs[k],G.arcs[k][j].adj};
closedge[k].lowcost=0;
for(i=1;i<G.vexnum;i++) 
{
for(j=0;j<G.vexnum;j++)
{
if(closedge[j].lowcost>0)
k=j;
break;
}
for(j=0;j<G.vexnum;j++)
{
if(closedge[j].lowcost>0)
if(closedge[j].lowcost<closedge[k].lowcost)
k=j;
}
printf("%c %c",closedge[k].adjvex,G.vexs[k]);
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[k][j].adj<closedge[j].lowcost)
closedge[j]={G.vexs[k],G.arcs[k][j].adj};
}
}
return G;
}
int main()
{
Graph G;
creatgraph(G);
primtree(G);
}

#2


#include<stdlib.h>
#include<stdio.h>
#define maxnum 20
typedef struct ArcCell
{
int adj;
}ArcCell,Adj[maxnum][maxnum];
typedef struct
{
char vexs[maxnum];
Adj arcs;
int vexnum,arcnum;
}Graph;
int locate(Graph G,char v)
{
for(int i=0;i<G.vexnum;i++)
if(v==G.vexs[i])
return i;
}
Graph creatgraph(Graph G)
{
int i,j,w,k;
char v,u;
printf("请输入顶点数和边数\n"); 
scanf("%d%d",&G.vexnum,&G.arcnum);
fflush(stdin);
printf("请输入顶点\n");
for(i=0;i<G.vexnum;i++){
printf("请输入第%d个顶点",i+1); 
scanf("%c",&G.vexs[i]);
fflush(stdin);
}
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
G.arcs[i][j].adj=32767;
}
for(k=0;k<G.arcnum;k++){
printf("请输入第%d对值\n",k+1);
scanf("%c%c%d",&v,&u,&w);
i=locate(G,v);
j=locate(G,u);
G.arcs[i][j].adj=w;
fflush(stdin);}
}
Graph primtree(Graph G)
{
int i,j,k;
struct{
char adjvex;
int lowcost;
}closedge[20];
k=3;
for(j=0;j<G.vexnum;j++)
if(j!=k)
closedge[j]={G.vexs[k],G.arcs[k][j].adj};
closedge[k].lowcost=0;
for(i=1;i<G.vexnum;i++) 
{
for(j=0;j<G.vexnum;j++)
{
if(closedge[j].lowcost>0)
k=j;
break;
}
for(j=0;j<G.vexnum;j++)
{
if(closedge[j].lowcost>0)
if(closedge[j].lowcost<closedge[k].lowcost)
k=j;
}
printf("%c %c",closedge[k].adjvex,G.vexs[k]);
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[k][j].adj<closedge[j].lowcost)
closedge[j]={G.vexs[k],G.arcs[k][j].adj};
}
}
return G;
}
int main()
{
Graph G;
creatgraph(G);
primtree(G);
}