近段时间又回顾了下数据结构中的图，我之前的有一篇博文介绍了图与线性表和树的区别与联系。
并且就图的存储和图的创建也做了一些简单的说明，
这一篇我将着重说说图的两种基本的遍历方法，深度遍历和广度遍历。
深度遍历：
深度遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有顶点未曾被访问，则深度遍历可从图中
某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有与v有路径的顶点都被访问到，若此时
图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。
其具体的代码实现如下：
|
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
27
28
29
30
31
32
|
int
DFSTraverse(MGraph G)
{
int
v;
printf
(
"\n深度遍历输出 : \n"
);
for
(v = 0; v < G.vexnum; v++)
{
visited[v] = 0;
}
for
(v = 0; v < G.vexnum; v++)
{
if
(visited[v] == 0)
{
DFS(G, v);
printf
(
"\n"
);
}
}
return
true
;
}
int
DFS(MGraph G,
int
v)
{
int
w;
visited[v] = 1;
printf
(
"%s "
, G.vexs[v]);
for
(w = 0; w < G.vexnum; w++)
{
if
(G.arcs[v][w].adj ==1 && visited[w] == 0)
{
DFS(G,w);
}
}
return
true
;
}
|
其实质是运用了递归思想，在遍历图中时，对图中的每个顶点之多调用一次DNS函数，因为一旦某个顶点呗标志城已被访问，
就不再从它出发进行搜索了，因此遍历图的实质上是对每个顶点查找器邻接点的过程。
广度遍历：
广度优先搜索遍历类似于树的按层次遍历的过程。假设从图中某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别
从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先与“后被访问的邻接点”被访问，直至图中所有已被访问的邻接点都被访问到，
若此时图中尚有顶点未被访问到，则另选图中一个未被访问的顶点作为起始点，重复上述操作，直至图中所有顶点都被访问到为止。
其具体代码实现如下：
|
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
int
QueueInit(Queue *sq)
{
if
(sq)
{
sq->front = 0;
sq->rear = 0;
}
else
return
false
;
return
true
;
}
int
QueueIsEmpty(Queue sq)
{
if
(sq.front == sq.rear)
return
true
;
else
return
false
;
}
int
EnQueue(Queue *sq,
int
x)
{
if
(sq->front == (sq->rear+1)%MAX_VERTEX_NUM)
{
printf
(
"Queue is full!\n"
);
return
false
;
}
else
{
sq->data[sq->rear] = x;
sq->rear = (sq->rear+1)%MAX_VERTEX_NUM;
}
}
int
OutQueue(Queue *sq)
{
if
(QueueIsEmpty(*sq))
{
printf
(
"Queue is Empty!\n"
);
return
false
;
}
else
{
sq->front = (sq->front+1)%MAX_VERTEX_NUM;
}
}
int
QueueFront(Queue sq,
int
*e)
{
if
(QueueIsEmpty(sq))
{
printf
(
"Queue is full!\n"
);
return
false
;
}
else
{
*e = sq.data[sq.front];
return
true
;
}
}
int
BFSTraverse(MGraph G)
{
int
v;
printf
(
"广度遍历 : \n"
);
for
(v = 0; v < G.vexnum; v++)
{
visited[v] = 0;
}
for
(v = 0; v < G.vexnum; v++)
{
if
(visited[v] == 0)
{
BFS(G, v);
printf
(
"\n"
);
}
}
return
true
;
}
int
BFS(MGraph G,
int
v)
{
int
v1, v2;
Queue sq;
QueueInit(&sq);
EnQueue(&sq, v);
visited[v] = 1;
printf
(
"%s "
, G.vexs[v]);
while
(QueueIsEmpty(sq) ==
false
)
{
QueueFront(sq, &v1);
OutQueue(&sq);
for
(v2 = 0; v2 < G.vexnum; v2++)
{
if
(G.arcs[v1][v2].adj != 0 && visited[v2] == 0)
{
EnQueue(&sq, v2);
visited[v2] = 1;
printf
(
"%s "
, G.vexs[v2]);
}
}
}
return
true
;
}
|
对于图的广度优先遍历的试下来说，运用了队列的特点，每一个顶点之多进一次队列，便利图的实质上是通过边或者弧
找邻接点的过程。
从上可以看出，其实广度遍历和深度遍历它们两者的时间复杂度是一样的，两者的不同之处仅仅在于对顶点访问的顺序不同而已。
本文转自 驿落黄昏 51CTO博客，原文链接：http://blog.51cto.com/yiluohuanghun/836495，如需转载请自行联系原作者
