深度优先搜索

深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。这个名称直接来自于这个算法的操作方式：它沿着某一路径深入遍历直到无法继续，然后再回溯进行下一条路径的遍历。

• DFS的主要思想是“尽可能深地搜索”，当搜索至某一节点时，就尽可能深入地去搜索它的每一个子节点。

DFS在以下几类问题中有广泛应用：

• 路径查找：在图或树中查找从一个节点到另一个节点的路径，或者查找满足特定条件的路径。

• 连通性问题：在图中检测两个节点是否连通，或者计算图中连通分量的数量。

• 拓扑排序：DFS可以用于有向图的拓扑排序，即对有向图的节点进行排序，使得对每一条有向边(u, v)，u都在v之前。

• 寻找强连通分量：在有向图中，使用Tarjan算法或Kosaraju算法，都会用到DFS来寻找强连通分量。

• 求解组合问题：例如求解全排列、组合等问题，DFS可以用于遍历所有可能的解空间。

• 回溯问题：DFS经常被用于回溯算法中，例如解数独、八皇后问题等。

基本的DFS算法非常简单，只需要递归地访问每个节点及其未访问过的邻居即可。但是，根据特定问题的需求，DFS的实现可能会变得更复杂，比如需要添加一些额外的数据结构来记录信息，或者需要修改遍历的顺序等。

需要注意的是，DFS不保证找到的是最短路径，如果需要找到最短路径，通常会使用宽度优先搜索（Breadth-First Search，简称BFS）或Dijkstra算法等其他算法。

深度优先搜索题目清单

• 《程序员面试金典（第6版）》面试题 16.19. 水域大小（深度优先搜索，类似棋盘类问题，八皇后的简化版本，C++）