图搜索算法：深度优先查找

gaunthan Posted on Feb 17 2017

? Searching ? ? Algorithm ?

> **深度优先查找**(Depth First Search, DFS)是穷举查找、无信息图查找算法的一种，用来系统地遍历图中的所有顶点和边。

## 思想
深度优先查找可以从任意顶点开始访问图的顶点，然后把该顶点标记为已访问(visited)。每次迭代的时候，该算法紧接着处理与当前顶点邻接的未访问顶点（如果有若干个这样的邻接未访问顶点，可以任意选择其中一个。在实际应用中，这种选择是由表示图的数据结构决定的。）。这个过程一直持续，直到遇到一个终点——该顶点的所有邻接顶点都已被访问过。在该顶点上，该算法沿着来路后退一条边，并试着继续从那里访问未访问的顶点。在后退到起始顶点，并且起始顶点也是一个终点时（所有邻接顶点都被访问过了），该算法终止运行。这样，起始顶点所在的连通分量的所有顶点都被访问过了。如果还存在未访问的顶点，则该算法必须从其中任一顶点开始，重复上述过程。

## 示例
示例如下：
![](https://leanote.com/api/file/getImage?fileId=58a6613eab64414b06002906)[^DFS Sample]

[^DFS Sample]:[Methods of Search](http://www.cse.unsw.edu.au/~billw/Justsearch.html).

## 伪代码
以下是深度优先查找遍历的伪代码，它能够输出每个顶点第一次被遍历的顺序：
```cpp
// 实现给定图的深度优先查找遍历
// @input   图G = <V, E>
// @output  图G的顶点，按照被DFS遍历第一次访问到的先后次序，用连续的整数标记
DFS(G)
    将V中的每个顶点标记为0，表示还未被访问
    count = 0
    for each vertex v in V do
        if v is marked with 0
            dfs(v)

// 递归访问所有和v相邻接的未访问顶点，然后按照count的值给它们标序    
dfs(v)
    ++count; mark v with count
    for each vertex w in V adjacant to v do
        if w if marked with 0
            dfs(w)
```

## 迭代实现
仔细观察上面代码展示的遍历过程，会发现它符合后进先出(LIFO)的特点，因此深度优先查找过程可以用一个栈来将其递归实现转换为迭代实现。

1. 在一开始，我们初始化一个空栈。在选择了一个初始顶点后，我们将它标记为已访问，随后把它入栈。
2. 接着我们将该栈顶顶点的一个邻接的、未被访问的顶点标记为已访问后入栈，然后选择存放在栈顶的顶点重复这一过程。如果存放在栈顶的顶点没有满足要求的邻接顶点，则它已经成为了一个终结点，这时候我们把它弹出栈，并选择新的栈顶顶点重复本过程，直到栈为空。
3. 当栈空时，我们已经遍历完了初始顶点所在的连通分量。因此，这一步骤我们选择一个仍未被访问的结点重新开始即可。

可知我们需要修改的算法是`dfs()`，其修改后的伪代码如下：
```cpp
dfs(v)
    ++count; mark v with count
    initialize a stack with v
    while the stack is not empty do
        v = get top vertex of stack
        if v has adjacant node w in V that marked with 0
            ++count; mark w with count
            add w to the stack
        else
            remove the top vertex from stack
```

## 效率分析
深度优先查找消耗的时间和用来表示图的数据结构的规模是成正比的：

- 对于邻接矩阵表示法，因为每一个顶点都要进行$|V|$次的判断（以决定该顶点有哪些邻接顶点），而这样的顶点有$|V|$个，因此时间效率属于$\theta(|V|^2)$。
- 而对于邻接链表表示法，因为每个顶点判断邻接顶点时不需要先找到邻接顶点，使得所有判断邻接顶点是否已访问的操作次数等于边的数目，因此它属于$\theta(|V|+|E|)$。

上面的$|V|$和$|E|$分别是图的顶点和边的数量。

## 应用
### 检查图的连通性
因为DFS在访问了所有和初始顶点有路径相连的顶点之后就会停下来，所以我们可以这样检查一个图的连通性：从任意一个结点开始DFS遍历，在该算法停下来以后，检查是否所有的顶点都被访问过了。如果都访问过了，那么这个图是连通的；否则，它是不连通的。

### 获取图的连通分量
上面的过程再推广一步，就可以用来找到一个图的连通分量。当算法停下来时，检查是否所有的顶点都被访问过了。如果都访问过，则这个图只有一个连通分量；否则，图有多个连通分量，而当前已经访问过的结点构成了一个连通分量，接着任意选择一个未访问结点重复本过程。

### 判断图是否无环
如果图是无环的，则执行深度优先查找的过程中，当前结点的邻接顶点应该都是未访问的（除了其父结点，即上一个被访问结点）。如果满足这个条件，则图无环；否则，图有环。

## See Also

- [图搜索算法：广度优先查找](http://leanote.com/blog/post/58a65844ab64414b060027c6)

## References

- 莱维汀, A.). 算法设计与分析基础(第3版)[M]. 清华大学出版社, 2015.