前言
本章将介绍图的表示和图的搜索。图的搜索指的是系统化地跟随图中的边来访问图中的每个结点。图搜索算法可以用来发现图的结构。许多的图算法在一开始都会先通过搜索来获得图的结构，其他的一些图算法则是对基本的搜索加以优化。可以说，图的搜索技巧是整个图算法领域的核心。
图的表示
对于图 G = (V,E)，有两种标准表示方法。一个邻接表的集合和一个邻接矩阵，即邻接表表示(adiacent-list representation)和邻接矩阵表示adiacent-matrix representation)。它们每一个都可以表示有向图和无向图。
- 对于稀疏图(sparse graph)：当|E| « |V|2时通常用邻接表表示。
- 对于稠密图(dense graph)：|E| 与 |V|2相近。通常用邻接矩阵表示。
如下图，是对图(1)的邻接表(2)和邻接矩阵(3)的表示：
广度优先搜索（BFS）
广度优先搜索(breadth-first search)是最简单的图算法之一，也是许多重要的图算法原型，Prim最小生成树算法和Dijkstra单源最短路径算法都使用了类似广度优先搜索的思想。
给定一个图 G =(V,E)和一个源(source)点 s，广度优先搜索系统性地探索 G 的边去“发现”所有从源点出发可到达的顶点，并计算从源点到每一个可达(reachable)顶点v的距离，该距离等于从s到v经过的最少的边的数量。广度优先搜索生成一棵以s为根并包含所有可达顶点的“广度优先树”，树中从s 到v的简单路径对应从s到v的最路径。广度优先搜索算法既可以用于有向图，也可以用于无向图。
BFS的搜索过程是一层一层向外的，就犹如水波(wave)一样，例如：
简单来说，对于BFS的过程如下：
- 从s开始，一层一层地发现顶点。
- 首先访问距离s只有1条边的所有顶点(s的下一层)。
- 从那些顶点开始，访问距离下一层的所有顶点，以此类推。
- 直到它发现了从s出发可到达的每个顶点。
为此，我们还是用一个队列Q来记录需要访问的顶点。
下面给出广度优先搜索过程中，需要给每个顶点v添加额外属性:
- v.color 表示的颜色: WHITE(该顶点未被发现)、GRAY（表示其邻接顶点可能还有未发现顶点）或BLACK（表示其邻接顶点全部被发现），初始所有顶点为白色。第一次发现某顶点，该顶点变为灰色，即该顶点被发现，所有灰色顶点构成搜索边界。当与某个顶点相连的所有边都被发现后，该顶点变为黑色。
- v.d 表示从s到v的距离。
- v.π 表示v的在广度优先树中的前驱，若v为源点或者未被发现，故v没有前驱，初始设v.π = NIL。
下面是BFS的伪代码：
BFS(G, s)
for each vertex u ∈ G.V - {s}
u.color = WHITE
u.d = ∞
u.π = NIL
s.color = GRAY
s.d = 0
s.π = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ≠ ∅
u = DEQUEUE(Q)
for each vertex v in G.Adj[u] // search the neighbors of u
if v.color == WHITE // is v being discovered now?
v.color = GRAY
v.d = u.d + 1
v.π = u
ENQUEUE(Q, v) // v is now on the frontier
u.color = BLACK这个过程非常容易理解，我们通过一个例子来解释这个过程。
例如下图，我们把源点设为3，我们需要画的是BFS过程中每个节点的d值和π值，以及队列Q的出队顺序。
- 初始化情况下，我们把所有点的距离设置为∞，前驱π设置为NIL。
- 从3开始，我们先把3加入队列Q中，Q = 3。
- 对于3的下一层有两个节点5和6，把它们加入队列中（数字默认从小到大），并设置它们的距离d为1，前驱为3，3出队，于是现在就有了： Q = 5,6; 5.d = 6.d = 1; 5.π = 6.π = 3；
- 节点5出队，同时节点4入队，并设置4.d = 2, 4.π = 5，于是此时有Q = 6,4；
- 节点6出队，它没有下一层节点了于是无事发生，Q = 4；
- 节点4出队，同时节点2入队，并设置2.d = 3, 2.π = 4，于是此时有Q = 2；
- 节点2出队，它没有下一层节点了于是无事发生，队列Q为空，BFS结束；
最后可以得到这样的表：
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| v.d | ∞ | 3 | 0 | 2 | 1 | 1 |
| v.π | NIL | 4 | NIL | 5 | 3 | 3 |
Q出队的顺序为：3,5,6,4,2
我们发现，节点1没有被BFS访问到，因为没有一个节点的下一层是它。它的d还是初始的∞，π还是NIL。
故：BFS不一定访问所有的节点。
深度优先搜索（DFS）
深度优先搜索(depth-first search)优先沿着从最近发现的顶点v发出的一条边进行探索，尽管该顶点可能还有其他边未被探索。一旦从v发出的所有边都被探索后，则需要回溯(backtrack)到到达v的前一个顶点进行继续探索。不断执行上述过程，直到从源点可达的所有顶点全部被发现若还有顶点未被发现，选择未被发现的顶点中的任一顶点作为新的源点继续上述过程。深度优先搜索重复以上全部过程直到所有顶点全部被发现。
简单来说。DFS则是先探索一条道路到头，再回溯到分叉口进行其他探索。
与BFS不同的是，DFS必须访问所有的顶点，所以可能深度优先搜索有多个源点。还有广度优先搜索的前驱子图是一棵树，但是深度优先搜索的前驱子图可能包含若干棵树，这是由于搜索可能从多个源点进行。
除了之前BFS的d外，深度优先搜索还给每个顶点加时间戳(timepstamp)。
每一个顶点v有两个时间戳：第一个时间戳v.d记录了v第一次被发现的时间(discovery time)，此时变灰，第二个时间戳v.f 记录了v被搜索结束的时间(finish time)，此时变黑。
故此时有如下算法：
DFS(G)
for each vertex u ∈ G.V
u.color = WHITE
u.π = NIL
time = 0
for each vertex u ∈ G.V
if u.color == WHITE
DFS-VISIT(G, u)
DFS-VISIT(G, u)
time = time + 1 // white vertex u has just discovered
u.d = time
u.color = GRAY
for each vertex v ∈ G.Adj[u] // explore each edge (u, v)
if v.color == WHITE
v.π = u
DFS-VISIT(G, v)
time = time + 1
u.f = time
u.color = BLACK // blacken u; it is finished我们同样通过一个例子来了解DFS的过程，设有如下的图，假设我们按照字典序建立邻接表：
- 按照字典序，先从u开始遍历，一路探索到头可以得到：u: 1/NIL, v: 2/NIL, y: 3/NIL, x: 4/NIL. 此时到了x已经无路可走了。
- 从x回溯到分叉口，我们发现这个路径(u->v->y->x)没有分叉口到新的节点，故一路回到u，此时：u: 1/8, v: 2/7, y: 3/6, x: 4/5
- 我们发现从u开始遍历的已经结束了，查看邻接表中，按照字典序，下一个没被遍历到的节点是w，于是从w开始继续遍历。
- 从w开始，发现只有z没被访问过，于是路径为w->z，有：w: 9/NIL, z: 10/NIL
- 此时同样到了z后无路可走了，于是原路返回有：w: 9/12, z: 10/11，至此我们所有的节点就访问完毕了。
最终图：
d/f表：
| u | v | w | x | y | z | |
|---|---|---|---|---|---|---|
| d | 1 | 2 | 9 | 4 | 3 | 10 |
| f | 8 | 7 | 12 | 5 | 6 | 11 |
后记
本章介绍了图的搜索算法，包括广度优先搜索和深度优先搜索。广度优先搜索通过按层次遍历图的节点，形成广度优先树，并记录节点的距离和前驱节点。深度优先搜索通过优先探索一条路径到底，然后回溯到分叉口进行其他探索，直到遍历所有节点。这两种搜索算法在图算法中具有重要的应用，如Prim最小生成树算法和Dikstra单源最短路径算法。通过掌握这些算法的原理和实现，可以更好地理解和解决各种图相关问题，提高算法效率。图的搜索是图算法领域的核心内容，对于进步学习和应用图算法具有重要意义。
Comments NOTHING