解释代码( { int i,j; char v1,v2; int c; printf("请输入(Vi,Vj)对应的顶点及长度:\n"); cin>>v1>>v2>>c; //输入一条边依附的两个顶点及权值 Edge[k].Head=v1; Edge[k].Tail=v2; Edge[k].lowcost=c; i = LocateVex(G,v1); j = LocateVex(G,v2);//确定v1和v2在G中的位置,即顶点数组的下标 //G.arcs[i][j]=G.arcs[j][i]=c; G.arcs[i][j]=c; //边<v1,v2>的权值置为c G.arcs[j][i]=G.arcs[i][j]; //置<v1,v2>的对称边<v2,v1>的权值为c } //for } //辅助数组的定义,用来记录从顶点集U到V-U的权值最小的边 typedef struct Closedge { VerTexType adjvex; //最小边在U中的那个顶点 ArcType lowcost; //最小边上的权值 }closedge[MVNum]; int Min(closedge SZ,AMGraph G) //求出第k个顶点,closedge[k]中存有当前最小边 { int i=0,j,k,min; while(!SZ[i].lowcost) i++; min=SZ[i].lowcost; k=i; for(j=i+1;j<G.vexnum;j++) { if(SZ[j].lowcost>0) { if(min>SZ[j].lowcost) { min=SZ[j].lowcost; k=j; } } } return k; })
时间: 2024-04-21 22:27:00 浏览: 89
这段代码是为了实现Prim算法中的辅助数组和Min函数。
Closedge是一个结构体数组,用于记录从顶点集U到V-U的权值最小的边,包括最小边在U中的那个顶点和最小边上的权值。
Min是一个函数,用于求出第k个顶点,closedge[k]中存有当前最小边。具体实现是通过遍历closedge数组,找到lowcost值最小的那个顶点k,并返回其下标。其中,SZ表示closedge数组,G表示邻接矩阵表示的无向图。
这段代码主要用于Prim算法中的最小生成树部分,实现了辅助数组和求最小边的函数,供后续的Prim算法使用。
相关问题
解释代码( for(int k=0;k<G.arcnum;k++) { int i,j; char v1,v2; int c; printf("请输入(Vi,Vj)对应的顶点及长度:\n"); cin>>v1>>v2>>c; //输入一条边依附的两个顶点及权值 Edge[k].Head=v1; Edge[k].Tail=v2; Edge[k].lowcost=c; i = LocateVex(G,v1); j = LocateVex(G,v2); G.arcs[i][j]=G.arcs[j][i]=c; } } typedef struct Closedge { VerTexType adjvex;//最小边在U中的那个顶点 ArcType lowcost;//最小边上的权值 }closedge[MVNum]; int Min(closedge SZ,AMGraph G)//求出第k个顶点,closedge[k]中存有当前最小边 { int i=0,j,k,min; while(!SZ[i].lowcost) i++; min=SZ[i].lowcost; k=i; for(j=i+1;j<G.vexnum;j++) { if(SZ[j].lowcost>0) { if(min>SZ[j].lowcost) { min=SZ[j].lowcost; k=j; } } } return k; } void prim(AMGraph G,VerTexType u)//p算法 {//无向图G以邻接矩阵形式存储,从顶点u出发构造G的最小生成树T,输出T的各条边 closedge closedge; int k=LocateVex(G,u);//k为顶点u的下标 for(int j=0;j<G.vexnum;j++)//对V-U的每一个顶点vj,初始化closedge[j] { closedge[j].adjvex=u; closedge[j].lowcost=G.arcs[k][j]; } closedge[k].lowcost=0;//初始,U={u} )
这段代码实现了Prim算法,用于求解无向图的最小生成树。首先,通过for循环和LocateVex函数输入每条边的信息,包括边的起点、终点和权值,并将这些信息存储在Edge数组中。接下来,定义了一个结构体Closedge用于存储最小生成树的各个节点的信息,包括最小边在U中的那个顶点和最小边上的权值。Min函数用于求出第k个顶点,closedge[k]中存有当前最小边。最后,prim函数用于构造最小生成树,首先对V-U的每个顶点vj进行初始化,将closedge[j].adjvex设置为起点u,将closedge[j].lowcost设置为起点u到vj的距离。然后将起点u加入U中,将closedge[k].lowcost设置为0,表示已经访问过。
#include <stdio.h> #define INFINITY 32768 typedef enum{DG,DN,UDG,UDN}GraphKind; #define MaxVexNum 20 //最大顶点数目 typedef char ElemType; typedef struct { ElemType vexs[MaxVexNum]; int arcs[MaxVexNum][MaxVexNum]; int vexnum, arcnum; }AMGraph; typedef struct ArcNode{ int adj; }ArcNode; int locate(AMGraph G,char v) { int k; for(k=0;k<G.vexnum;k++) { if(G.vexs[k]==v) { return k; } } return -1; } void CreatMGraph(AMGraph G) { int i,j,k; char v1,v2; scanf("%d%d",&G.vexnum,&G.arcnum); getchar(); for(i=0;i<G.vexnum;i++) { for(j=0;j<G.vexnum;j++) { G.arcs[i][j]=0; } } for(i=0;i<G.vexnum;i++) { scanf("%c",&G.vexs[i]); } getchar(); for(k=0;k<G.arcnum;k++) { scanf("%c%c",&v1,&v2); getchar(); i=locate(G,v1); j=locate(G,v2); G.arcs[i][j]=1; G.arcs[j][i]=1; } } int visited[MaxVexNum]; void DepthFirstSearch(AMGraph g,int v0) { printf("%c",g.vexs[v0]);visited[v0]=1; for(int vj=0;vj<g.vexnum;vj++) { if(!visited[vj]&&g.arcs[v0][vj]==1) { DepthFirstSearch(g,vj); } } } void TraverseGraph(AMGraph g) { for(int vi=0;vi<g.vexnum;vi++) { visited[vi]=0; } for(int vi=0;vi<g.vexnum;vi++) { if(!visited[vi]) DepthFirstSearch(g,vi); } } int main() { AMGraph G; CreatMGraph(G); TraverseGraph(G); return 0; }哪错了
在该程序中存在以下问题:
1. 在函数 `CreatMGraph` 中,应该传入指针类型的参数 `AMGraph *G`,否则函数中对 `G` 的修改不会影响到主函数中的 `G` 变量。
2. 在 `CreatMGraph` 中,应该使用 `scanf("%d%d",&G->vexnum,&G->arcnum);` 以及 `scanf(" %c",&G->vexs[i]);` 和 `scanf("%c%c",&v1,&v2); getchar();`,其中 `%d` 和 `%c` 之间应该加上空格,否则会有输入格式上的问题。
3. 在 `DepthFirstSearch` 函数中,应该在递归调用前先进行标记,否则会死循环或者输出结果不正确。
修改后的代码如下所示:
```c
#include <stdio.h>
#include <stdlib.h>
#define INFINITY 32768
#define MaxVexNum 20
typedef char ElemType;
typedef enum {DG, DN, UDG, UDN} GraphKind;
typedef struct {
ElemType vexs[MaxVexNum];
int arcs[MaxVexNum][MaxVexNum];
int vexnum, arcnum;
} AMGraph;
void CreatMGraph(AMGraph *G) {
int i, j, k;
char v1, v2;
scanf("%d%d", &G->vexnum, &G->arcnum);
getchar();
for (i = 0; i < G->vexnum; i++) {
for (j = 0; j < G->vexnum; j++) {
G->arcs[i][j] = 0;
}
}
for (i = 0; i < G->vexnum; i++) {
scanf(" %c", &G->vexs[i]);
}
getchar();
for (k = 0; k < G->arcnum; k++) {
scanf("%c%c", &v1, &v2);
getchar();
i = locate(*G, v1);
j = locate(*G, v2);
G->arcs[i][j] = 1;
G->arcs[j][i] = 1;
}
}
int locate(AMGraph G, char v) {
int k;
for (k = 0; k < G.vexnum; k++) {
if (G.vexs[k] == v) {
return k;
}
}
return -1;
}
int visited[MaxVexNum];
void DepthFirstSearch(AMGraph g, int v0) {
visited[v0] = 1;
printf("%c", g.vexs[v0]);
for (int vj = 0; vj < g.vexnum; vj++) {
if (!visited[vj] && g.arcs[v0][vj] == 1) {
DepthFirstSearch(g, vj);
}
}
}
void TraverseGraph(AMGraph g) {
for (int vi = 0; vi < g.vexnum; vi++) {
visited[vi] = 0;
}
for (int vi = 0; vi < g.vexnum; vi++) {
if (!visited[vi]) {
DepthFirstSearch(g, vi);
}
}
}
int main() {
AMGraph G;
CreatMGraph(&G);
TraverseGraph(G);
return 0;
}
```
阅读全文
相关推荐

















