图的深度优先遍历

图这一章我一直觉得自己学的不是很好。。。这次就只放代码,不敢多说什么了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
typedef int Boolean;			//Boolean是布尔类型,其值为TRUE 或者FLASE
Boolean visited[MAXVEX]; //访问标志的数组


/*邻接矩阵的深度优先递归算法*/
void DFS(GraphAdjList G, int i){
EdgeNode *p;
visited[i] = TRUE;
printf("%c", G.adjList[i].data); //打印定点,也可以是其它操作
p = G.adjList[i].firstedge;
while (p){
if (!visited[p->adjvex])DFS(G, p->adjvex); //对未访问的邻接顶点递归调用
p = p->next;
}
}

/*邻接矩阵的深度遍历操作*/
void DFSTraverse(GraphAdjList G){
int i;
for (i = 0; i < G.numVertexes; i++){
visited[i] = FALSE; //初始化所有顶点状态都是未访问的状态
}
for (i = 0; i < G.numVertexes; i++){
if (!visited[i])DFS(G, i); //对未访问过的顶点调用DFS,若连通图,只会执行一次
}
}