图的DFS与BFS遍历：像逛游乐场一样走遍所有节点

图就像一张“关系网”，里面有很多小圆点（节点），圆点之间用线（边）连起来。比如你的班级里，每个同学是一个节点，两个人是好朋友就画一条边。图的遍历就是按照某种顺序，一个不漏地把所有节点都走一遍，并且每个节点只访问一次。这有点像你去一个游乐场，想玩遍所有项目，但又不想重复排同一个队。

由于图里可能存在“回路”（比如A和B互相认识，B和C认识，C又认识A），如果瞎走就会来回转圈。所以我们需要一个“已访问”标记，就像在游乐场的项目门口打卡，打过卡的项目就不再进去了。

下面我们用Python实现两种最常用的遍历方法：深度优先搜索（DFS） 和 广度优先搜索（BFS）。注意图可能不连通，比如班级里分成几个小圈子，彼此不认识。这时候我们要对每个还没访问的小圈子都启动一次搜索，才能走遍所有人。

1. 图长什么样？—— 用“邻居列表”表示图

在电脑里，最常用的表示图的方法是邻接表。每个节点后面跟一个列表，里面写着它的“邻居”是谁。

比如下面这个图：节点0和1、2相连，节点1和0、3相连，节点3和1、4相连。

# 用邻接表表示图，每个节点对应一个列表，列表里是它直接相连的节点
graph = {
    0: [1, 2],   # 节点0的朋友是1和2
    1: [0, 3],   # 节点1的朋友是0和3
    2: [0],      # 节点2的朋友只有0
    3: [1, 4],   # 节点3的朋友是1和4
    4: [3]       # 节点4的朋友只有3
}

我们可以把节点看成“人”，列表里的数字就是“好朋友”。遍历就是挨个去认识所有人。

2. 深度优先搜索（DFS）—— 一条路走到黑

DFS很像“探洞”：从入口进去，一直往深处走，直到没路了，再退回来换另一条岔路继续走。它使用递归（或者自己用栈）来实现。

生活例子：你从家里出发，想去拜访所有亲戚。你决定先走一条路，走到最远的亲戚家，再回来走另一条路。这样就不会漏掉任何一家。

代码实现（递归版）

# 记录已经访问过的节点，用集合避免重复访问
visited_dfs = set()

def dfs_traverse(node):
    """深度优先遍历：从当前节点出发，递归访问所有没去过的邻居"""
    visited_dfs.add(node)                # 标记当前节点已访问
    print("DFS访问:", node)              # 输出访问顺序，可以换成其他处理
    for neighbor in graph[node]:         # 遍历当前节点的所有邻居
        if neighbor not in visited_dfs:  # 如果邻居没去过
            dfs_traverse(neighbor)       # 继续深入访问邻居

# 因为图可能不连通，所以对每个节点都尝试作为起点
for node in graph:
    if node not in visited_dfs:
        dfs_traverse(node)

运行结果（从0开始）：

DFS访问: 0
DFS访问: 1
DFS访问: 3
DFS访问: 4
DFS访问: 2

你会发现：先跑到了最深的4，然后才回来访问2。这就是“一路走到黑”的效果。

3. 广度优先搜索（BFS）—— 一层一层向外扩

BFS就像病毒传播或者朋友圈扩散：先感染离你最近的人，然后这些人再去感染他们的邻居，再感染邻居的邻居……一层一层向外扩。它使用队列（先进先出）来实现。

生活例子：你新到一个班级，想快速认识所有人。你可以先认识自己的同桌（第一层），然后让同桌介绍他们的朋友（第二层），再让这些朋友介绍他们的朋友……这样一层一层就认识了所有人。

代码实现（队列版）

from collections import deque   # 引入双端队列，专门用来做BFS

visited_bfs = set()             # 记录已访问的节点

# 遍历所有节点，保证不连通图也能全部走完
for start in graph:
    if start in visited_bfs:
        continue                # 如果这个节点已经访问过，跳过
    queue = deque([start])      # 起点入队
    visited_bfs.add(start)      # 标记起点已访问
    while queue:                # 只要队列不为空
        node = queue.popleft()  # 取出队首节点
        print("BFS访问:", node) # 输出
        for neighbor in graph[node]:           # 遍历这个节点的所有邻居
            if neighbor not in visited_bfs:    # 如果邻居没去过
                visited_bfs.add(neighbor)      # 标记已访问（防止重复入队）
                queue.append(neighbor)         # 邻居入队，等待后续访问

运行结果（从0开始）：

BFS访问: 0
BFS访问: 1
BFS访问: 2
BFS访问: 3
BFS访问: 4

看到没？先访问离0最近的1和2，然后才是3，最后是4。就像水波一样一圈一圈荡开。

4. 为什么要有“for 所有节点”的循环？

很多新手只写 dfs_traverse(0) 或 queue = deque([0])，觉得从0出发就能走遍全图。但是如果图不连通，比如有节点5和6单独组成一个小团体，和0-4没有边，那么从0出发根本走不到5和6。

所以我们在外层套一个循环：对所有节点挨个尝试作为起点，如果它还没被访问过，就启动一次搜索。这样即使图分成好几块（多个连通分量），也能全部遍历完。

5. 新手常犯的错误

❌ 忘记标记“已访问”

def dfs_traverse(node):
    # 忘了写 visited_dfs.add(node) 
    for neighbor in graph[node]:
        if neighbor not in visited_dfs:
            dfs_traverse(neighbor)

这样会导致死循环（比如0和1互相访问，永远出不来）。

❌ BFS中把邻居标记放在“出队时”而不是“入队时”

while queue:
    node = queue.popleft()
    visited_bfs.add(node)          # 错误：等到出队才标记
    for neighbor in graph[node]:
        if neighbor not in visited_bfs:
            queue.append(neighbor)

这样同一个节点可能会被多次加入队列（因为还没标记，它的邻居可能重复把它加进去），导致大量重复计算，甚至无限循环。正确做法：在入队时就标记。

❌ 递归深度过大导致程序崩溃

如果图非常深（比如一条直线，有上万个节点），递归DFS会占用大量栈空间，Python默认递归深度约1000，超过会报 RecursionError。此时应该改用栈模拟（非递归DFS）。例如：

stack = [start]
while stack:
    node = stack.pop()
    if node not in visited:
        visited.add(node)
        for neighbor in graph[node][::-1]:  # 反转顺序保持和递归一致
            if neighbor not in visited:
                stack.append(neighbor)

❌ 没有处理“孤立节点”

如果一个节点没有任何边（比如节点6: []），遍历时不会出错，但它的邻居列表为空，所以直接访问它然后结束。外层循环依然能覆盖它。

6. 完整可运行的示例代码

下面把DFS和BFS合在一起，加上一些额外节点演示不连通图，并打印出访问顺序。

from collections import deque

# 构建一个图，包含两个独立的小团体
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1],
    4: [],          # 孤立节点
    5: [6],
    6: [5, 7],
    7: [6]
}

print("===== DFS 遍历 =====")
visited_dfs = set()                     # 记录DFS已访问的节点
def dfs_traverse(node):
    visited_dfs.add(node)               # 标记当前节点
    print("DFS访问:", node)
    for neighbor in graph[node]:
        if neighbor not in visited_dfs:
            dfs_traverse(neighbor)

for node in graph:
    if node not in visited_dfs:
        dfs_traverse(node)

print("\n===== BFS 遍历 =====")
visited_bfs = set()                     # 记录BFS已访问的节点
queue = deque()

for start in graph:
    if start in visited_bfs:
        continue
    queue.append(start)
    visited_bfs.add(start)
    while queue:
        node = queue.popleft()
        print("BFS访问:", node)
        for neighbor in graph[node]:
            if neighbor not in visited_bfs:
                visited_bfs.add(neighbor)
                queue.append(neighbor)

运行结果示例：

===== DFS 遍历 =====
DFS访问: 0
DFS访问: 1
DFS访问: 3
DFS访问: 2
DFS访问: 4
DFS访问: 5
DFS访问: 6
DFS访问: 7

===== BFS 遍历 =====
BFS访问: 0
BFS访问: 1
BFS访问: 2
BFS访问: 3
BFS访问: 4
BFS访问: 5
BFS访问: 6
BFS访问: 7

注意：DFS和BFS都完整覆盖了所有8个节点（包括孤立节点4以及5-7小团体）。

7. 学到DFS和BFS之后，还能学什么？

求最短路径：在无权图中，BFS天然能求出从起点到每个点的最短路径（因为它是按层数递增的）。
连通分量：上面遍历的每个“for循环”里走的那些节点就构成了一个连通分量。数一数循环启动了几次，就知道图分成了几块。
拓扑排序：对有向无环图（DAG），可以用DFS或BFS（Kahn算法）来排出一个顺序，比如安排课程的学习顺序。
二分图判断：用BFS或DFS给节点涂色，如果相邻节点颜色相同就不是二分图。

这些内容都是图论里最实用的部分，掌握了DFS和BFS，就等于拿到了图论的地图导航。快去试试自己画一张班级的朋友关系图，用代码遍历一下吧！

例题精讲