Question

数据结构C++无向图的邻接矩阵深度优先遍历,求解答

#include <iostream>#include <malloc.h>using namespace std;#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20#define OK -1#define FALSE 0#define TRUE 1typedef int Status;typedef int Boolean ;typedef int VertexType;typedef enum {UDG} GraphKind;
typedef struct{ VertexType vexs[MAX_VERTEX_NUM]; int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vexnum,arcnum;
}MGraph;int LocateVex (MGraph G,VertexType v){ int i; for(i = 0;i<G.vexnum;i++) if(G.vexs[i] == i){ return i; } return -1;}void CreateUDG(MGraph&G){ int i,j,k,v1,v2; printf("请输入顶点的数："); cin>>G.vexnum; printf("请输入边的数目："); cin>>G.arcnum; printf("请输入顶点的值："); for(i = 0;i<G.vexnum;i++) cin>>G.vexs[i]; for(i = 0;i<G.vexnum;i++) for(j = 0;j<G.vexnum;j++) G.arcs[i][j] = 0; printf("请输入边依附的顶点编号："); for(k = 0;k<G.arcnum;k++){ cin>>v1>>v2; i = LocateVex(G,v1); j = LocateVex(G,v2); G.arcs[i][j]==1; G.arcs[i][j] = G.arcs[j][i] ; }}bool visited[MAX_VERTEX_NUM];
int FirstAdjVex(MGraph G,int v){ int j; for(j = 0;j<G.vexnum;j++) { if(G.arcs[v][j] == 1) return j;} return -1;}int NextAdjVex(MGraph G,int v,int w){ int j; for(j = w+1;j<G.vexnum;j++){ if(G.arcs[v][j] == 1) return j;} return -1;}
void DFS(MGraph G,int v){ int w; visited[v] = TRUE; cout<<G.vexs[v]<<endl;
for(w = FirstAdjVex(G,v);w>=0;w = NextAdjVex(G,v,w)) if(!visited[w]) DFS(G,w);}
void DFSTraverse(MGraph G,int v){ for(v = 0;v<G.vexnum;++v) visited[v] = FALSE; for(v = 0;v<G.vexnum;++v) if(!visited[v]) DFS(G,v);}

int main(){ int v = 0; MGraph G; CreateUDG(G);
DFSTraverse(G,v); system("PAUSE"); return 0;}

运行的结果

不管输入顶点的值是什么，深度遍历的结果都是输入顶点的值的顺序。。
数据结构的新手，求大神指导

Answer 1

你能不能给贴上一个深度遍历错误的用例？你这个输入用例的结果就是1，2，3，4
现在能看出来的就是这个了，
int LocateVex (MGraph G,VertexType v){
int i;
for(i = 0;i<G.vexnum;i++)
if(G.vexs[i] == v){ //这里应该是等于v，而不是等于i
return i;
}
return -1;
}

追问

没有啊，我按照你说的改了，可是还是同样的结果

大神，求指导！！！

追答

我都说过啦。。你这个测试用例的输入返回的结果就是1234啊，你找一个输入用例不是1234的，最好节点多一点儿的测试用例。然后把结果贴一下我看看。

追问

追答

代码给你改完了，在下面，改过的地方我加了注释，不过你输入的边不要加“-“，否则会读入一个负数，那就不成了。
int LocateVex (MGraph G,VertexType v){
int i;
for(i = 0;i>G.vexnum;
printf("请输入边的数目：");
cin>>G.arcnum;
printf("请输入顶点的值：");
for(i = 0;i>G.vexs[i];
for(i = 0;i>v1>>v2;
i = LocateVex(G,v1);
j = LocateVex(G,v2);
G.arcs[i][j] =1;
G.arcs[j][i] = G.arcs[i][j] ;//这里是j,i=i,j 而不是你的i j= j i，按你的话整个邻接矩阵都是0了
}
}
}
后面都没错了