深度优先搜索

深度优先搜索（depth-first search，DFS）从一个顶点出发，沿尚未访问的邻点继续前进，走到不能再前进时逐层退回。它适合遍历可达区域、构造搜索树以及进一步研究环和连通性。DFS 找到的是一条路径，通常不是最少边数路径；这一点与广度优先搜索不同。

一条走到底的访问链

沿用图论中的一张小无向图：顶点 S、A、B、C、D、E、F，边 SA、SB、AC、AD、BD、CE、DE，F 孤立。每个顶点的邻接点按字母顺序读取。从 S 开始，首次进入顶点的顺序为 S、A、C、E、D、B；回退次序为 B、D、E、C、A、S。若要把全图都走完，最后还需从未访问的 F 再启动一次。

无向图中深度优先搜索从S依次首次进入A、C、E、D、B，F作为第二棵搜索树；虚线表示未选入搜索树的原图边 — 箭头表示这次搜索首次进入顶点的方向，不表示原图的边是单向的。虚线保留了原图中的其他连接。

DFS 的前驱给 B 留下的搜索树路径是 S→A→C→E→D→B，走了 5 条边；原图却有 SB 这条直接边，最少只走 1 条。图中虚线 SB 正是这个反例。若任务要求从 S 到 B 的最少边数，应使用 BFS，而不能把 DFS 的第一条路径当作最短路。

已访问标记与回退

进入一个顶点时立即标记，随后依邻接顺序检查；遇到已标记的点就跳过。调用栈保存尚未检查完邻点的顶点，所以在 B 没有新邻点时，程序自然退回 D，再退回 E。对本例，进入与离开的时间顺序分别是：

顶点	S	A	C	E	D	B	F
进入次序	1	2	3	4	5	6	7
离开次序	6	5	4	3	2	1	7

上表的“次序”分别按进入事件和离开事件单独计数；它不是同一只时钟的绝对时刻。把 F 加入后，全图得到两棵搜索树：一棵覆盖 S、A、B、C、D、E，另一棵只有 F。对于无向图，这两棵树恰对应两个连通分量；若改成有向图，按顶点顺序产生的 DFS 森林不能直接当作强连通分量。

遍历覆盖与代价

每个顶点只在第一次进入时标记，因此不会重复递归。若从 S 可达的某个顶点最终仍未访问，沿一条从 S 到它的路径找第一个未访问顶点；它的前一个顶点已经访问，检查那条边时就应进入它，矛盾。所以一次搜索会覆盖起点的整个可达区域；对剩余顶点再次启动，便覆盖整张有限图。

邻接表中每个顶点只进入一次，每条无向边最多从两端各检查一次，时间为 $O (V + E)$ 。已访问集合、前驱和递归栈合计 $O (V)$ 额外空间。递归深度最坏可达 $V$ ；Python 对很深的图有递归深度限制，处理大型图时可换成显式栈，但仍须保持相同的“首次进入”与邻点次序约定。

深度优先搜索的回退

沿搜索树走到尽头，再沿调用栈逐层返回。

静态配图与完整推导见本节正文；交互演示需浏览器启用 JavaScript。

Python 实现

输入邻接表包括所有顶点和各自按字母顺序排列的邻点。代码返回首次进入顺序、完成退出顺序，以及搜索树中的前驱；最后的断言把正文的两棵树和 B 的路径复算一遍。

Python 3

def dfs_forest(graph):
    visited = set()
    parent = {}
    entered = []
    exited = []

    def visit(u):
        visited.add(u)
        entered.append(u)
        for v in graph[u]:
            if v not in visited:
                parent[v] = u
                visit(v)
        exited.append(u)

    for root in graph:
        if root not in visited:
            parent[root] = None
            visit(root)
    return entered, exited, parent


if __name__ == "__main__":
    graph = {
        "S": ["A", "B"], "A": ["C", "D", "S"],
        "B": ["D", "S"], "C": ["A", "E"],
        "D": ["A", "B", "E"], "E": ["C", "D"], "F": [],
    }
    entered, exited, parent = dfs_forest(graph)
    assert entered == ["S", "A", "C", "E", "D", "B", "F"]
    assert exited == ["B", "D", "E", "C", "A", "S", "F"]
    path = []
    vertex = "B"
    while vertex is not None:
        path.append(vertex)
        vertex = parent[vertex]
    assert list(reversed(path)) == ["S", "A", "C", "E", "D", "B"]

本例无向图里，已访问且不是当前顶点前驱的邻点提示存在环；返回父顶点的原路边不能据此算一个环。在有向图中进一步判环时，还要区分“正在递归栈中”与“已经退出”的顶点，只看见访问标记不够。图的方向和所要判断的性质改变后，条件也必须跟着改变。

参考资料

TheAlgorithms/Python：depth_first_search.py；同仓库的另一种实现。本文用一张与 BFS 共用的图独立编写代码。
Sedgewick、Wayne，Undirected Graphs：DFS 路径、连通分量及与 BFS 的区别。
先修：图论、算法与复杂度；对照：广度优先搜索。