预计阅读本页时间：-
深度优先搜索
考虑图6-7左边的迷宫。在经过一些尝试后，一个孩子能够快速地找到从起点s到终点t的路。但是计算机解决这个问题看起来就比较复杂，一种方法是假设离目标并不太远，然后做尽可能多的深度移动。也就是说，只要可以，随机选择一个方向，然后向这个方向前进，标记一下起点。如果你走上一条死路，或者不能在不重新访问顶点的情况下做任何深度移动，那么就会退到另一条未访问的分支上，并且向这个方向前进。图6-7右边的数字表示的是一个解的分支点；事实上，在这个解中，我们访问了迷宫中的所有点。
我们能够用一个包含了点和边的图来表示图6-7的迷宫。一个顶点表示迷宫中的每一个分支点（在图6-7的右边用数字标记），当然也包括“末路点”。如果迷宫中在两个顶点之间存在一条有向路，并且在这个方向上没有其他的选择，那么我们就说存在一条边。从图6-7得到的迷宫的无向图表示如图6-8所示，每一个顶点都有一个唯一标识符。
为了解决这个问题，我们需要知道在图G=(V,E)的顶点s到顶点t间是否存在一条路。本例中，所有的边都是无向的，但是即使在迷宫上加一些限制条件，我们也能够非常容易地将其看成有向图。
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
图6-9的详解包括了用伪代码描述的深度优先搜索。深度优先搜索的核心是递归的dfs_visit(u)操作，这个操作访问之前没有访问过的顶点u。并且这个操作通过对顶点染色记录下了搜索进程。顶点可能会染成如下三种颜色：
白色
顶点还未访问。
灰色
顶点已经被访问过了，但是其可能还有没有被访问过的顶点。
黑色
顶点以及其所有的邻接顶点都已经被访问过了。
首先，所有的顶点初始为白色，然后深度优先搜索在源顶点s上调用dfs_visit。在对u所有的未访问邻接顶点（它们为白色）递归调用dfs_visit之前，dfs_visit(u)将u染成灰色。一旦这些递归调用完成，那么我们将u染成黑色，然后函数返回。当递归函数dfs_visit返回，深度优先搜索开始回溯，直到回溯到一个有邻接顶点未被访问过的顶点（事实上，回溯到标记为灰色的顶点）。
对有向和无向图来说，深度优先搜索从s开始，访问了图中所有s可达的顶点。如果G中仍然有未访问，但是从s不可达的顶点存在，深度优先搜索将会随机从其中选择一个作为源点，然后重复操作。这个过程将会一直重复，直到G中所有的顶点都被访问。
在这个执行过程中，深度优先搜索遍历图中的边，计算和复杂的图结构有关的信息。深度优先搜索维护一个计数器，在一个顶点第一次被访问（标记为灰色）和完成在这个顶点上的深度优先搜索（标记为黑色）时，这个计数器增加计数。对于每个顶点，深度优先搜索记录如下信息。
pred[v]
前驱顶点，用来恢复从源点s到顶点v的路。
discovered[v]
其值为当深度优先搜索第一次访问v时，计数器增加后的值，简写为d[v]。
finished[v]
其值为完成在这个顶点v上的深度优先搜索，计数器增加后的值，简写为f[v]。
顶点访问的顺序将会改变计数器的值，所以需要注意邻接节点的顺序。对很多构建在深度优先搜索上的算法，深度优先搜索计算出来的信息都是非常有用的，包括拓扑排序，寻找强连通部，寻找网络中潜在的弱点。让我们来看看图6-8，假设顶点的邻接顶点是升序排列。那么计算出来的信息如图6-10所示。当计数器为18，顶点8正在被访问时，让我们看看图中顶点的颜色。图中有些部分（例如标记为黑色的点）已经被完全搜索并且不会被重复访问。我们需要注意白色顶点的d都将大于18（因为它们现在还没有被访问），以及黑色顶点的f都小于等于18，因为它们已经被完全搜索过，灰色顶点的d小于等于18，f大于18，因为它们现在正处于某条递归访问的路上。
深度优先搜索没有对图的一个整体认识，所以它是盲目地搜索顶点＜5，6，7，8＞，即使是南辕北辙。一旦深度优先搜索结束，pred[]的值能够用来生成一条从任意顶点到源点s的路。当然，这条路也许不会是最短路径，例如＜s，1，3，4，5，9，t＞，但是最短的路径是＜s，6，5，9，t＞[1]。
输入/输出
输入
一个图G=(V，E)，源点是s∈V。n表示的是G中的顶点数。
输出
深度优先搜索计算三个数组。d[v]表示的是v第一次被访问时，计数器的值。pred[v]是深度优先搜索时，顶点v的先驱顶点。f[v]则是当v被完全访问过之后，计数器的值，即dfs_visit(v)之后计数器的值。如果原图是不连通的，那么根据pred[]的值实际上可以得到一个由深度优先树组成的深度优先森林。对于森林中的树来说，它们根节点的pred[r]的值都为-1。
假设
此算法对于有向图和无向图同样适用。
