查看“︁深度优先搜索”︁的源代码

'''深度优先搜索'''（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 再启动一次。

[[File:Gezhi-dfs-tree.svg|frame|center|alt=无向图中深度优先搜索从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。对本例，进入与离开的时间顺序分别是：

{| class="wikitable"
! 顶点 !! 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 到它的路径找第一个未访问顶点；它的前一个顶点已经访问，检查那条边时就应进入它，矛盾。所以一次搜索会覆盖起点的整个可达区域；对剩余顶点再次启动，便覆盖整张有限图。

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

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

<pre class="algorithm-code">
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"]
</pre>

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

== 参考资料 ==
* [https://github.com/TheAlgorithms/Python/blob/c27e95123cb7e2fef5b15e64b5e800201cc7665c/graphs/depth_first_search.py TheAlgorithms/Python：depth_first_search.py]；[https://github.com/TheAlgorithms/Python/blob/c27e95123cb7e2fef5b15e64b5e800201cc7665c/graphs/depth_first_search_2.py 同仓库的另一种实现]。本文用一张与 BFS 共用的图独立编写代码。
* [https://algs4.cs.princeton.edu/41graph/ Sedgewick、Wayne，Undirected Graphs]：DFS 路径、连通分量及与 BFS 的区别。
* 先修：[[图论]]、[[算法与复杂度]]；对照：[[广度优先搜索]]。
[[分类:算法]]