元数据卡

• 前置知识：图基础（前页）
• 预计时间：20 分钟
• 核心难度：进阶
• 完成标志：能自己写出 DFS 和 BFS 遍历，理解栈和队列的区别，能找出连通分量

---

你的进度

上一页你知道了图是什么——节点和边的网。但知道了地图长什么样和能在上面走路是两回事。你面前有一片森林，兽道交错，你站在营地 A（索引 0），目标营地 E（索引 4）。有没有路？哪条最近？

先看一个简单的图：

A→B→C，A→D，D→E，B→F，F→E

索引映射：0=A, 1=B, 2=C, 3=D, 4=E, 5=F

这不是树——从 A 出发，你有两条路线到 E：A→B→F→E 和 A→D→E。两条路都能到 E，但路径不同。

这就是图遍历要解决的问题：给定一个起点，如何访问所有（或特定）可达节点？

---

你的任务

学会两种遍历方式：DFS（深度优先，沿着一条路走到底再回头）和 BFS（广度优先，一圈圈扩散）。然后会发现一个附加福利——BFS 在无权图中直接找到最短路径，而 DFS 擅长检测连通分量。

---

破局 · 溯源

第一战：DFS——摸到最深处再回头

DFS 的逻辑"像你走进一个山洞的分岔路，每一次都选最左边那条走到头，死路了退回来试右边那条"。

用代码实现，用栈（Stack）：

# Python: DFS（迭代版，显式栈）
def dfs(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(f"访问 {node}")
            # 倒序入栈，保持从左到右的遍历顺序
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    return visited

# 图：A→B→C，A→D，D→E，B→F，F→E
graph = {
    'A': ['B', 'D'],
    'B': ['A', 'C', 'F'],
    'C': ['B'],
    'D': ['A', 'E'],
    'E': ['D', 'F'],
    'F': ['B', 'E']
}

print("DFS 从 A 出发:")
dfs(graph, 'A')

运行步骤：

1. 保存为 dfs_demo.py
2. 运行 python3 dfs_demo.py

预期输出：

DFS 从 A 出发:
访问 A
访问 B
访问 C
访问 F
访问 E
访问 D

注意遍历顺序：A → B（第一个邻居）→ C（B的第一个邻居）→ 回溯到B → F → E → 回溯到A → D。

栈的变化过程：

初始: stack = [A]
pop A, push B,D(倒序) → stack = [D, B]
pop B, push C,F(倒序) → stack = [D, C, F]
pop F, push B,E(跳过已访问B) → stack = [D, C, E]
pop E, push D(跳过) → stack = [D, C]
pop C → stack = [D]
pop D → stack = []

---

DFS 递归版

递归版本更简洁，但有深度限制（Python 默认约 1000 层）：

# Python: DFS（递归版）
def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(f"访问 {node}")
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    return visited

同样的图调用 dfs_recursive(graph, 'A')，输出和迭代版一致。什么时候用递归？教学和小规模数据。生产环境一律用迭代版（显式栈）避免栈溢出。

---

第二战：BFS——投石入水，一圈圈扩散

BFS 的逻辑完全相反：不是往深处扎，而是像水面上的波纹一样，一圈圈往外扩散。

BFS 用队列（Queue）。在无权图中，BFS 第一次到达某个节点时走的路径一定是最短的（边数最少）：

# Python: BFS
from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(f"访问 {node}")
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

print("\nBFS 从 A 出发:")
bfs(graph, 'A')

运行步骤：将代码追加到 dfs_demo.py 底部或保存为 bfs_demo.py 后运行。

预期输出：

BFS 从 A 出发:
访问 A
访问 B
访问 D
访问 C
访问 F
访问 E

注意和 DFS 的天壤之别：

• DFS: A → B → C → F → E → D（沿着一条路到底）
• BFS: A → B → D → C → F → E（按距离：A距离0，B和D距离1，C、F距离2，E距离3）

队列的变化过程：

初始: queue = [A]
pop A, push B,D → queue = [B, D]
pop B, push C,F → queue = [D, C, F]
pop D, push E → queue = [C, F, E]
pop C → queue = [F, E]
pop F, push E(已访问跳过) → queue = [E]
pop E → queue = []

---

栈 vs 队列：两种世界观

DFS = 栈（后进先出）= "一条路走到底，走不通回头"
BFS = 队列（先进先出）= "逐层扩散，近的先看"

对比维度	DFS（栈）	BFS（队列）
数据结构	栈（LIFO）	队列（FIFO）
遍历顺序	深度方向	层次方向
空间复杂度	O(h) 树高	O(w) 最大宽度
无权图最短路径	不保证	第一次到达即最短
适合场景	连通分量、拓扑排序、可达性	最短路径、层级遍历、社交距离
实现复杂度	递归 5 行 / 迭代 15 行	15 行
环检测	需 visited 集合	需 visited 集合

一条实战法则："能不能到"选 DFS，"多远能到"选 BFS。

---

第三战：连通分量——图里有多少个孤岛？

一个森林可能分成几块互不相通的区域——A-B 是一条兽道网，C-D 是另一条，中间没有路。每一块就是一个连通分量。

找出连通分量的方法极其简单：对所有未访问节点分别启动一次 DFS，每次启动找到的就是一个新分量：

# Python: 找出所有连通分量
def connected_components(graph):
    visited = set()
    components = []

    def dfs_component(start):
        component = []
        stack = [start]
        while stack:
            node = stack.pop()
            if node not in visited:
                visited.add(node)
                component.append(node)
                for neighbor in reversed(graph[node]):
                    if neighbor not in visited:
                        stack.append(neighbor)
        return component

    for node in graph:
        if node not in visited:
            comp = dfs_component(node)
            components.append(comp)
            print(f"连通分量: {comp}")

    return components

# 不连通图：三个互不相连的区域
forest = {
    'A': ['B'],
    'B': ['A'],
    'C': ['D'],
    'D': ['C'],
    'E': []
}

print("森林中的连通分量:")
connected_components(forest)

运行步骤：

1. 保存为 components.py
2. 运行 python3 components.py

预期输出：

森林中的连通分量:
连通分量: ['A', 'B']
连通分量: ['C', 'D']
连通分量: ['E']

A-B 是一条兽道，C-D 是另一条，E 独自一个营地——三个"世外桃源"，互不相通。

实战价值：社交网络中的朋友圈检测、地图中的孤立区域标记、网络拓扑中的断连节点发现。

---

常见陷阱

• DFS 递归爆栈：树的深度超过 1000 时用迭代版。Python 默认递归深度约 1000。
• BFS 不要用 list.pop(0)：pop(0) 是 O(n) 操作（挪动后续所有元素），用 collections.deque 的 popleft() 才是 O(1)。
• visited 检查时机：入栈/入队时就检查 visited，不要在 pop 时才检查——否则同一个节点可能被多次加入栈。
• 有向图的连通分量：这里讲的是无向图的连通分量。有向图需要分"强连通分量"（SCC）和"弱连通分量"，用 Kosaraju 或 Tarjan 算法——那是进阶内容。

---

旅人笔记

DFS 用栈深入到底再回头，擅长连通性检测和可达性分析。BFS 用队列逐层扩散，无权图中找到的就是最短路径。找连通分量只要遍历所有未访问节点，每启动一次新遍历就找到一个新分量。记住：栈 = 深入，队列 = 扩散。

下一步

图能遍历了，但"最短"才是你真正想要的——不仅仅是边数最少，而是权重和最小。森林里兽道有长有短，走哪条路能最快到另一个营地？

看最短路径 ->