//GraphDepth.cpp--page 157 7.1(b)
//Depth_First Search
#include < stdio.h >
#include < stdlib.h >
#include "ghl1.h"
#define MAX_VERTEX_NUM 20
typedef int VRType;
typedef int VertexType;
typedef struct ArcCell {
VRType adj;
}
ArcCell,
AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,
arcnum;
}
MGraph;
Status CreateUDN(MGraph & G);
int LocateVex(const MGraph & G, VertexType v);
void DFSTraverse(const MGraph & G, Status( * Visit)(const MGraph & G, int v));
void DFS(const MGraph & G, int i);
int FirstAdjVex(const MGraph & G, int i);
int NextAdjVex(const MGraph & G, int i, int w);
Status PrintVex(const MGraph & G, int i);
int visited[MAX_VERTEX_NUM];
Status( * VisitFunc)(const MGraph & G, int v);
int main(void) {
MGraph G;
printf("\n");
CreateUDN(G);
DFSTraverse(G, PrintVex);
return 0;
}
Status CreateUDN(MGraph & G) {
int i,
j,
k;
VertexType v1,
v2;
printf("Enter vertex number:");
scanf("%d", &G.vexnum);
printf("Enter arc number:");
scanf("%d", &G.arcnum);
for (i = 0; i < G.vexnum; i++) {
printf("Enter %d vertex:", i + 1);
scanf("%d", &G.vexs);
}
for (i = 0; i < G.vexnum; i++) for (j = 0; j < G.vexnum; j++) G.arcs[j].adj = 0;
for (k = 0; k < G.arcnum; k++) {
printf("Enter %d arc:\n", k + 1);
printf("Enter the first vertex:");
scanf("%d", &v1);
printf("Enter the second vertex:");
scanf("%d", &v2);
i = LocateVex(G, v1);
j = LocateVex(G, v2);
G.arcs[j].adj = G.arcs[j].adj = 1;
}
return OK;
}
int LocateVex(const MGraph & G, VertexType v) {
int i = 0;
while (G.vexs != v) i++;
if (i < G.vexnum) return i;
else return INFEASIBLE;
}
void DFSTraverse(const MGraph & G, Status( * Visit)(const MGraph & G, int v)) {
int i;
VisitFunc = Visit;
for (i = 0; i < G.vexnum; i++) visited = FALSE;
for (i = 0; i < G.vexnum; i++) if (!visited) DFS(G, i);
}
void DFS(const MGraph & G, int i) {
int w;
visited = TRUE;
VisitFunc(G, i);
for (w = FirstAdjVex(G, i); w >= 0; w = NextAdjVex(G, i, w)) if (!visited[w]) DFS(G, w);
}
int FirstAdjVex(const MGraph & G, int i) {
int j;
for (j = 0; j < G.vexnum; j++) if (G.arcs[j].adj == 1) return j;
return INFEASIBLE;
}
int NextAdjVex(const MGraph & G, int i, int w) {
int j;
for (j = w + 1; j < G.vexnum; j++) if (G.arcs[j].adj == 1) return j;
return INFEASIBLE;
}
Status PrintVex(const MGraph & G, int i) {
printf("%5d", G.vexs);
return OK;
}
标签:vexnum,const,MGraph,int,return,++,GraphDepth From: https://blog.51cto.com/u_16076050/6195970