DFS深度优先搜索

What · 是什么

DFS（Depth First Search）是图/树遍历算法，从起点出发，每次尝试向更深的节点走，走到无路可走时回溯。通过递归调用自身或显式栈实现。每个节点仅访问一次（打访问标记）。DFS生成树是原图的一个生成树，其性质可用于求强连通分量、割点、桥等。DFS序列中每个子树对应连续区间，可用于树上问题。

Why · 为什么

How · 实现

伪代码

DFS(v):
  mark v as visited
  for u in neighbors(v):
    if u not visited:
      DFS(u)

Python 实现

import sys
sys.setrecursionlimit(1000000)

def dfs_recursive(adj, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for v in adj[start]:
        if v not in visited:
            dfs_recursive(adj, v, visited)
    return visited

def dfs_iterative(adj, start):
    visited = set()
    stack = [start]
    while stack:
        u = stack.pop()
        if u in visited:
            continue
        visited.add(u)
        for v in adj[u]:
            if v not in visited:
                stack.append(v)
    return visited

def dfs_tree_edges(adj, start):
    """Return DFS tree edges (parent, child)."""
    visited = set([start])
    edges = []
    def _dfs(u):
        for v in adj[u]:
            if v not in visited:
                visited.add(v)
                edges.append((u, v))
                _dfs(v)
    _dfs(start)
    return edges

if __name__ == "__main__":
    adj = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}
    r1 = dfs_recursive(adj, 0)
    r2 = dfs_iterative(adj, 0)
    assert r1 == r2 == {0, 1, 2, 3}, f"DFS failed: {r1}, {r2}"
    tree = dfs_tree_edges(adj, 0)
    assert len(tree) == 3
    # Disconnected graph: only reaches one component
    adj2 = {0: [1], 1: [0], 2: [3], 3: [2]}
    r3 = dfs_recursive(adj2, 0)
    assert r3 == {0, 1}, f"Discon DFS failed: {r3}"
    print("dfs: ALL TESTS PASSED")

易错点

• 递归深度限制：Python默认1000层，需setrecursionlimit或改用栈
• 邻接矩阵存储时时间退化为O(V^2)
• 迭代栈实现中，pop顺序可能导致访问顺序与递归不同（逆序压栈）
• 未标记已访问节点可能导致重复访问/死循环

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/dfs/
• CP-Algorithms✓ https://cp-algorithms.com/graph/depth-first-search.html
• 书籍✓ CPH ch12 pp127-132