邻接矩阵存储图的深度优先遍历.zip

#define MAX 20 int visited[MAX]; typedef struct ArcCell{ int adj; }ArcCell, AdjMatrix[MAX][MAX]; typedef struct{ char vexs[MAX]; AdjMatrix arcs; int vexnum, arcnum; }MGraph; MGraph create(){ MGraph G; int i, j; char c; printf("Please input vexnum and arcnum\n"); scanf("%d,%d", &i, &j); scanf("%c", &c); G.vexnum=i; G.arcnum=j; printf("Please input vexs[]\n"); for(i=0; i<G.vexnum; i++) scanf("%c", &G.vexs[i]); scanf("%c", &c); for(i=0; i<G.vexnum; i++){ for(j=0; j<G.vexnum; j++) G.arcs[i][j].adj=0; } for(i=0; i<G.arcnum; i++){ char m, n, p; int t, j; printf("Please input the arc\n"); scanf("%c,%c", &m, &n); scanf("%c",&p); for(t=0; t<=G.vexnum; t++) { if(G.vexs[t]==m) break; } for(j=0; j<=G.vexnum; j++) { if(G.vexs[j]==n) break; } if(t==G.vexnum||j==G.vexnum) { printf("error"); break; } G.arcs[t][j].adj=1; } return (G); } void print(MGraph G){ int i; printf(" "); for(i=0; i<G.vexnum; i++) printf(" %c", G.vexs[i]); printf("\n"); for(i=0; i<G.vexnum; i++) { int j; printf("%c", G.vexs[i]); for(j=0; j<G.vexnum; j++) printf(" %d", G.arcs[i][j].adj); printf("\n"); } } void DFS(MGraph G, int v){ int w; visited[v]=1; printf("%c ", G.vexs[v]); w=0; for(; w<G.vexnum; w++) if(G.arcs[v][w].adj&&!visited[w]) DFS(G, w); } void DFSTraverse(MGraph G){ int v; v=0; printf("DFSTraverse\n"); for(; v<G.vexnum; ++v) visited[v]=0; for(v=0; v<G.vexnum; ++v) if(!visited[v]) DFS(G, v); printf("\n"); } void BFSTraverse(MGraph G){ int stack[MAX]; int base, top, v; printf("BFSTraverse\n"); base=0; top=0; v=0; for(; v<G.vexnum; ++v) visited[v]=0; for(v=0; v<G.vexnum; ++v) if(!visited[v]) { visited[v]=1; printf("%c ", G.vexs[v]); stack[top]=v; top++; while(base!=top) { int w; w=0; for(; w<G.vexnum; w++) if(G.arcs[stack[base]][w].adj&&!visited[w]) { visited[w]=1; printf("%c ", G.vexs[w]); stack[top]=w; top++; } base++; } } printf("\n"); } MGraph G; main(){ int i; i=1; while(i){ printf("please input i\n"); scanf("%d", &i); switch(i){ case 1: { G=create(); break;} case 2: { print(G); break;} case 3: { DFSTraverse(G); break;} case 4: { BFSTraverse(G); break;} case 0: break; } } }