Python图的DFS遍历 - 七级 | C++ & Algorithm 编程研习社

深入理解图的深度优先搜索（DFS）——从迷宫到代码

你有没有玩过走迷宫？从入口进去，你沿着一条路一直走，遇到岔路先选一条，走到死胡同就原路返回，换一条没走过的路继续走。直到把所有能走的路都探完，这就是深度优先搜索（Depth-First Search，简称 DFS）。在编程中，DFS 用来探索图（比如社交网络、地图、文件目录）里的所有节点，就像你在迷宫里寻找每个角落一样。

DFS 的核心思想是：先一条路走到黑，再回头换路走。它天生适合用递归或栈来实现，因为这两者都能记住“走过的路”和“还没走的分叉口”。下面我们来一步步拆解。

1. 图是什么？先认识一下“地图”

在讲 DFS 之前，得先搞清楚我们的“地图”——图（Graph）。图由两部分组成：

节点（Vertex）：就像是地图上的城市、迷宫中的路口，或者社交网络里的一个人。
边（Edge）：连接两个节点的线，代表城市之间的道路、两个人之间的好友关系。

在代码里，我们常用 邻接表 来存图。邻接表就是一个字典：键是节点，值是一个列表，里面装着它直接相连的邻居节点。例如：

# 用邻接表表示一个无向图，每个节点连接着它的邻居
graph = {
    'A': ['B', 'C'],        # A 连接 B 和 C
    'B': ['A', 'D', 'E'],   # B 连接 A、D、E
    'C': ['A', 'F'],        # C 连接 A 和 F
    'D': ['B'],             # D 只连接 B
    'E': ['B', 'F'],        # E 连接 B 和 F
    'F': ['C', 'E']         # F 连接 C 和 E
}

这个图的结构像一个小网络：A 是中心，连接 B 和 C；B 又连着 D 和 E；C 连着 F；E 和 F 也相连。DFS 会沿着这些边一步步走。

2. DFS 的递归实现：用“函数调用栈”来记住回头路

递归是 DFS 最直观的写法。想象你站在一个岔路口（起点），你拿起纸笔：

在纸上写下“我已到过 A”。
看 A 有哪些路可以走（邻居），选一条没走过的（比如 B），走进去。
走到 B，重复第 1 步：写下“已到 B”，然后继续前进。
如果走到一个地方发现所有路都是走过的，就沿原路返回到上一个岔路口，再选另一条没走过的路。

在代码里，递归函数就扮演了“纸笔”和“返回”的角色。每次调用就相当于走进一个新节点，函数返回就相当于回到上一个节点。

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()                  # 用集合记录已访问节点，避免重复
    visited.add(start)                   # 标记当前节点为已访问
    print(start, end=' ')                # 输出访问顺序
    for neighbor in graph[start]:       # 遍历当前节点的所有邻居
        if neighbor not in visited:     # 如果邻居还没去过
            dfs(graph, neighbor, visited)  # 就继续往邻居走（递归）
    return visited

print("DFS遍历顺序：")
dfs(graph, 'A')  # 从 A 开始

运行这段代码，你会看到类似 A B D E F C 的输出。为什么是这个顺序？因为从 A 出发，先找第一个邻居 B，然后 B 的第一个邻居 D，D 没有其他路，返回 B；B 的第二个邻居 E，E 连接着 F（因为 F 还没去过），所以从 E 走到 F，F 还有一个邻居 C 还没去，所以最后到 C。整个过程就是“一条路走到头，再回头”。

注意：如果调整 graph 里邻居的顺序，输出顺序会变，但 DFS 的本质不变——总是先往深处走。

3. 迭代实现：用栈“手动”模拟递归

递归虽然好懂，但万一图很大（比如几万个节点），递归调用会占用系统栈，可能导致栈溢出。这时可以用显式的**栈（stack）**来模拟 DFS。

栈就像一摞盘子：后放上去的先拿走（后进先出）。我们用栈来存“下一步要访问的节点”，每次从栈顶取出一个节点，标记它，并把它的未访问邻居压入栈顶。这样后压入的邻居就会先被访问，正好实现了深度优先。

def dfs_iterative(graph, start):
    visited = set()                      # 记录已访问节点
    stack = [start]                      # 初始化栈，从起点开始
    while stack:
        vertex = stack.pop()             # 取出栈顶节点
        if vertex not in visited:
            visited.add(vertex)          # 标记已访问
            print(vertex, end=' ')       # 输出当前节点
            # 把未访问的邻居压入栈顶（注意顺序：为了和递归顺序一致，可以倒着压）
            for neighbor in reversed(graph[vertex]):  # 反向遍历，保持常见顺序
                if neighbor not in visited:
                    stack.append(neighbor)

print("迭代DFS遍历顺序：")
dfs_iterative(graph, 'A')

输出的顺序和递归版基本一致（取决于入栈顺序）。迭代版的好处是：完全控制了栈的大小，不会受递归深度限制。

4. 生活中的DFS：不只是走迷宫

打扫房间：你从卧室开始，先钻进床底下（深处），把角落的灰尘都擦干净，再退出来擦衣柜后面……直到卧室所有角落都搞定，才去客厅。
文件目录：在电脑里搜索某个文件，系统会先进入一个文件夹，再进入它的子文件夹，直到最底层，然后返回上一级，接着找下一个子文件夹——这就是 DFS。
数独求解：填一个数字，接着填下一个格子，如果走到死路（矛盾）就回退换一个数字再试。这种“试探 -> 回溯”就是 DFS 的思想（也叫回溯法）。

5. 新手最容易犯的 3 个错误

① 忘记标记已访问节点
如果不标记，DFS 会在有环的图里无限循环（比如A->B->C->A）。结果程序崩溃或者栈溢出。永远记得在访问节点时立刻加入 visited。

② 递归深度过大
如果图是一条长链（比如几万个节点连成一串），递归深度会超过 Python 的默认限制（约 1000 层）。解决方案：要么用迭代栈，要么手动设置递归深度：

import sys
sys.setrecursionlimit(100000)  # 调大递归限制，但慎用

③ 混淆有向图和无向图
上面例子是无向图（边没有方向）。如果是有向图（比如微博关注关系，A 关注 B 但 B 不一定关注 A），DFS 遍历时只能沿着箭头方向走。写代码前想清楚图是有向还是无向。

6. 完整可运行的代码示例（加上不同输入测试）

下面是一个完整的例子，包含递归和迭代两种 DFS，并测试一个更复杂的图（包含环和孤立节点？但为了简单，用之前的图）：

# 图的邻接表表示（无向）
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 递归版
def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    return visited

# 迭代版
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=' ')
            # 反向入栈保证顺序和递归接近
            for neighbor in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.append(neighbor)

print("递归DFS顺序：", end='')
dfs_recursive(graph, 'A')
print()

print("迭代DFS顺序：", end='')
dfs_iterative(graph, 'A')
print()

输出示例（可能因 Python 版本或邻居顺序略有差异）：

递归DFS顺序：A B D E F C 
迭代DFS顺序：A B D E F C

7. 相关指引：从 DFS 出发，还能学什么？

DFS 是图论中最重要的基础算法之一。学会了它，你可以继续了解：

广度优先搜索（BFS）：与 DFS 相反，它先访问离起点近的节点，再一层层向外扩散，适合找最短路径。比如，在社交网络里找“几度好友”。具体实现用队列，就像排队打饭——先来先服务。
Flood Fill 算法（洪水填充）：其实和 BFS/DFS 一模一样，只是作用在二维网格上。比如画图软件的油漆桶、扫雷游戏里点开空白区域。它的核心就是从一个点出发，向上、下、左、右（或包括对角线）扩散，把所有连通的同类格子都染上新颜色。

想深入研究，还可以看：

如何用 DFS 检测图中的环？
如何用 DFS 给图做拓扑排序（有向无环图）？
如何用 DFS 找出图中的连通分量？

DFS 就像一把万能钥匙，打开了图算法的大门。记住它的口诀：先深后广，遇道回头。多写几遍代码，你就能在迷宫般的图中自由穿梭了。

例题精讲