4.2 图的遍历：BFS 与 DFS

4.2 图的遍历：BFS 与 DFS

本节摘要：图遍历与树遍历的唯一本质差异是环——必须用 visited 记录已访问顶点，否则永远绕圈。BFS 借队列按层扩展，同一层即同一距离，无权图的最短步数由它直接给出；DFS 借递归或显式栈沿枝深入，适合连通性、路径存在性与"一条道走到黑"的问题。两者复杂度同为 O(V+E)（邻接表）。本节实现双雄并跟踪访问顺序。

环来了，树遍历的招式全要加一层保险

第三章的树遍历直接搬到图上会出什么事？画一个三角形 A-B-C-A：从 A 出发访问 B、C，C 的邻居里有 A——已经访问过，但树遍历没有"访问过"这个概念，于是再进 A，再进 B，再进 C……环让"已访问"从可选信息变成生死开关。图遍历的心法第一句：进门先领 visited 手环，访问过的顶点绝不再进。

领了手环之后，剩下的问题只是"按什么顺序走"。两种走法定下了图论半壁江山的节奏：

• 广度优先（BFS）：从起点出发，先访问所有一步邻居，再两步邻居，再三步……一圈圈向外推。发动机是队列（2.4 节）：先发现的先扩展；
• 深度优先（DFS）：沿着一条枝走到无路可走，退一步换条枝再走。发动机是递归栈（1.3 节）或显式栈。

# BFS 与 DFS：同一张图，两种访问顺序
from collections import deque

V = 7
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (5, 6)]
adj = [[] for _ in range(V)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)

def bfs(start):
    visited = [False] * V
    dist = [None] * V            # 顺手记账：离起点的步数
    q = deque([start])
    visited[start], dist[start] = True, 0
    order = []
    while q:                     # 队列非空就继续发牌
        u = q.popleft()          # 先进先出：保证按层
        order.append(u)
        for w in adj[u]:
            if not visited[w]:   # 手环检查：没访问过才入队
                visited[w] = True
                dist[w] = dist[u] + 1
                q.append(w)
    return order, dist

order, dist = bfs(0)
print("BFS 访问顺序：", order)
# 输出：BFS 访问顺序： [0, 1, 2, 3, 4, 5, 6]
print("各点离起点的步数：", dist)
# 输出：各点离起点的步数： [0, 1, 1, 2, 2, 2, 3]
​

BFS 的访问顺序 [0, 1, 2, 3, 4, 5, 6] 恰好是按层分组的：第零层只有起点，第一层是 1 与 2，第二层 3、4、5，第三层 6。dist 数组就是无权图最短步数——这是 BFS 最重要的副产品：每个顶点第一次被发现时，走的一定是步数最少的路线（更远的路线必然排在队列更后面）。

# DFS：递归版与显式栈版，访问顺序一致
def dfs_recursive(u, visited, order):
    visited[u] = True
    order.append(u)
    for w in adj[u]:                    # 邻居按邻接表顺序
        if not visited[w]:
            dfs_recursive(w, visited, order)

visited = [False] * V
order = []
dfs_recursive(0, visited, order)
print("DFS 访问顺序：", order)
# 输出：DFS 访问顺序： [0, 1, 3, 4, 2, 5, 6]
# 路线：0→1 走到底（3、4），退回 0 再走 2→5→6

def dfs_stack(start):
    visited = [False] * V
    order = []
    stack = [start]
    while stack:
        u = stack.pop()                 # 后进先出：栈顶优先深入
        if visited[u]:
            continue
        visited[u] = True
        order.append(u)
        for w in reversed(adj[u]):      # 反序入栈，保证弹出顺序与递归版一致
            if not visited[w]:
                stack.append(w)
    return order

print("显式栈 DFS 顺序：", dfs_stack(0))
# 输出：显式栈 DFS 顺序： [0, 1, 3, 4, 2, 5, 6]
​

两条路线的形状差异巨大：BFS 是同心圆扩散，DFS 是一条蛇钻迷宫。问"最少几步"用 BFS，问"连不连通、有没有路径"两者皆可，DFS 通常写起来更短。

两本熟悉的账：时间与栈深

时间账：邻接表上，每个顶点进出队/进出栈各一次（O(V)），每条边被两端各查看一次（O(E)），合计 O(V+E)。换成邻接矩阵，找邻居要扫整行，涨成 O(V²)——上一节选型账在这里兑现。

栈深账：递归 DFS 的栈深 worst 是 V（一条长链），大图上会触碰 Python 的递归限制（1.3 节的爆栈在图上重演）。工程上大图一律用显式栈版本，或改用 BFS。

# DFS 的副产品：连通分量计数
V2 = 8
edges2 = [(0, 1), (1, 2), (3, 4), (6, 7)]   # 5 号点孤立
adj2 = [[] for _ in range(V2)]
for u, v in edges2:
    adj2[u].append(v)
    adj2[v].append(u)

def components(n, adj):
    visited, comp = [False] * n, 0
    for s in range(n):                  # 每个没访问过的点开一次新遍历
        if not visited[s]:
            comp += 1
            stack = [s]
            visited[s] = True
            while stack:
                u = stack.pop()
                for w in adj[u]:
                    if not visited[w]:
                        visited[w] = True
                        stack.append(w)
    return comp

print("连通分量数：", components(V2, adj2))
# 输出：连通分量数： 4
# 分量一 0-1-2、分量二 3-4、分量三 6-7、分量四孤立的 5
​

走火入魔：三起遍历事故

事故一：入队与出队时机搞错。BFS 的 visited 必须在入队时置位，不是出队时。出队才置位的写法里，同一个顶点可能被多个邻居重复入队，队列膨胀、时间变慢，极端情况下重复访问计数爆炸。原则：标记要发生在"第一次被发现"，不是"被处理"。

**事故二：BFS 求带权最短路。**BFS 的层等于"步数"，只有每条边代价相同时步数才等于代价。边权不等（高速路与乡道）时要用 4.3 节的 Dijkstra；把 BFS 用在带权图上，得到的是"过路次数最少"而非"总代价最小"。

**事故三：在稠密大图上跑递归 DFS。**顶点百万的链状结构会把递归栈顶穿。纪律与 1.3 节相同：规模未知就默认显式栈，递归留给"深度可控"的场合（树、有界深度的搜索）。

💡 关键直觉：BFS 与 DFS 是同一张地图的两种展开策略，差别只在"待办清单"的数据结构——队列给你波纹，栈给你蛇。后面章节会反复见到这对组合：最短路用队列的纪律，回溯用栈的纪律。

本节要点回顾

• 环是图遍历与树遍历的分水岭：visited 记录从可选变成必须，且要在第一次发现时置位；
• BFS 按层扩展（队列驱动），dist 数组直接给出无权图最短步数；带权图不适用；
• DFS 沿枝深入（递归或显式栈），适合连通性、可达性与路径存在性；大图用显式栈防爆栈；
• 复杂度 O(V+E) 前提是邻接表；矩阵表示退化为 O(V²)；
• 连通分量是 DFS 的标准副产品：对每个未访问顶点启动一次遍历，启动次数即分量数。

遍历会走了，就能开始问"多远"。下一节给边加上权重，求网络里真正的最短路径。