深度优先搜索：一往无前的侦察路线

深度优先搜索：一往无前的侦察路线

一支侦察小队摸进陌生城区。带队者立下规矩：每到路口，任选未走过的方向一路深入，走不通就退回上个路口换方向，直到所有可达街巷都踏过一遍。这支小队执行的就是深度优先搜索。上一章我们把地图存好了，本节让侦察兵真正跑起来：给出递归与迭代两种实现，讲清时间戳与回溯这两件随身装备，并把复杂度账目算明白。它是后面连通性、环检测、拓扑排序共同的步法母体。

步法的三个要点

深度优先搜索的规则可以用三句话说完：

第一，到访即染色。每个顶点用颜色记状态：未发现的白色、正在探索的灰色、探索完毕的黑色。侦察兵只对白色顶点感兴趣。

第二，递归深入。站在灰色顶点上，翻它的邻居档案，见到白色邻居就立刻递过去，把自己的探索挂起。当前路径因此越拉越长，形成一条"深潜线"。

第三，回溯收尾。邻居档案翻完（没有白色邻居可去），顶点转黑，控制权交还上一级，从挂起处继续。挂起与恢复的次序恰好是后进先出——这就是"深度优先与栈同构"的原因：递归调用栈，或者一个显式栈，都能执行同一套规矩。

深度优先在图上犁出的访问轨迹，构成一棵深度优先树（图不连通时是森林）：树边是"发现新顶点"的边，其余边按指向祖先、指向子孙、横跨别枝分成几类。这个分类看似繁琐，却是第 4 章环检测与第 6 章拓扑排序的理论根基——有向图无环，当且仅当深度优先搜索全程不出现"指向灰色祖先的边"。时间上，邻接表存储下整套搜索的账单是顶点数加边数：每个顶点入栈出栈各一次，每条边的两端档案各被翻一次。

两种实现

先写教科书式的递归版，带发现与完成双时间戳：

import networkx as nx

def dfs_recursive(G, start):
    """递归深度优先：记录发现/完成时间戳与父指针"""
    color = {v: "白" for v in G.nodes}
    parent = {v: None for v in G.nodes}
    discover, finish = {}, {}
    clock = [0]                       # 用列表实现可变的“时钟”

    def visit(u):
        clock[0] += 1
        discover[u] = clock[0]
        color[u] = "灰"
        for v in G[u]:                # 翻邻居档案（邻接表计价）
            if color[v] == "白":
                parent[v] = u
                visit(v)              # 深潜：递归挂起当前探索
        color[u] = "黑"
        clock[0] += 1
        finish[u] = clock[0]

    visit(start)
    return parent, discover, finish

G = nx.Graph([("A","B"),("A","C"),("B","D"),("B","E"),("D","E"),("C","F")])
parent, d, f = dfs_recursive(G, "A")
print("父指针:", parent)
print("发现时间:", d)
print("完成时间:", f)
​

时间戳不是装饰品。完成时刻的倒序，就是有向无环图的一张拓扑序（第 6 章正式证明）；"灰到灰"的边暴露有向环（第 4 章）；某顶点的发现与完成区间是否被另一顶点的区间完全包含，还能判出"祖先与后代"——割点与桥的算法全靠这一条。

递归在深图上有栈深度的风险（Python 默认递归上限约千级），工程上常换显式栈版本：

def dfs_iterative(G, start):
    """显式栈版：与递归版访问同一批顶点（邻居序可能不同）"""
    seen = {start}
    stack = [start]
    order = []
    while stack:
        u = stack.pop()
        order.append(u)
        for v in reversed(list(G[u])):      # reversed 让顺序贴近递归版
            if v not in seen:
                seen.add(v)
                parent_v = v
                stack.append(v)
    return order

print("迭代版访问序:", dfs_iterative(G, "A"))
print("networkx 版:", list(nx.dfs_preorder_nodes(G, "A")))
​

两种版本访问的顶点集合必然相同（都是从起点可达的全体），但具体顺序可能因邻居处理顺序而不同——这提示我们：深度优先的"答案"是可达性，不是顺序。凡是依赖顺序的性质（如拓扑序），必须由时间戳这样的结构性信息保证，而不是碰运气的访问序。

演练：数连通块与找路径

用深度优先解决两个实际任务，作为步法的首次实战：

def count_components(G):
    """数连通块：对每个白点发起一次深度优先"""
    color = {v: "白" for v in G.nodes}
    def visit(u):
        color[u] = "灰"
        for v in G[u]:
            if color[v] == "白":
                visit(v)
        color[u] = "黑"
    blocks = 0
    for v in G.nodes:
        if color[v] == "白":
            blocks += 1
            visit(v)
    return blocks

archipelago = nx.Graph()
archipelago.add_edges_from([("岛A","岛B"), ("岛B","岛C"), ("岛D","岛E"), ("岛F","岛F" ) ])
print("群岛的连通块数:", count_components(archipelago))   # 第4章会正式立卷
​

def dfs_path(G, s, t):
    """找一条 s 到 t 的路径：深度优先 + 回溯还原"""
    parent = {s: None}
    stack = [s]
    while stack:
        u = stack.pop()
        if u == t:
            path = [t]
            while parent[path[-1]] is not None:
                path.append(parent[path[-1]])
            return path[::-1]
        for v in G[u]:
            if v not in parent:
                parent[v] = u
                stack.append(v)
    return None                      # 不可达

camp = nx.Graph([("营地","岔口1"), ("岔口1","岔口2"), ("岔口2","目标"),
                 ("营地","岔口3"), ("岔口3","目标"), ("岔口2","死胡同")])
print("行军路径:", " → ".join(dfs_path(camp, "营地", "目标")))
​

注意第二个函数返回的是"某条路径"，不是"最短路径"——深度优先可能先一头扎进远路。要最短，得请出下一节的包围网。

⚠️ 常见坑：递归深度优先在链状长图上会爆栈（数千顶点串成一线时几乎必爆）。竞赛代码里要么调大递归限制，要么直接写显式栈版；生产代码一律显式栈。

💡 关键直觉：深度优先的本质是"把图当作迷宫，用一根线团走完全程"。线团就是递归栈；线团收放之间留下的结构信息（时间戳、父子关系），比访问顺序本身值钱得多。

侦察兵的深潜步法已经练熟。下一节换一种队形：不再单兵深入，而是层层合围——广度优先搜索将带来"层次"这个新装备。