Hello 算法：Python 图深度优先遍历（DFS）递归实现逐行解析与 Pythontutor 可视化

本文以 Hello 算法仓库中的 graph_dfs.md 为核心素材，完整还原该文件内嵌在 Pythontutor 可视化链接中的 Python 深度优先遍历程序，逐行讲解递归辅助函数 dfs、访问集合 visited 与邻接表 GraphAdjList 的协作机制；并结合仓库中的标准实现 graph_dfs.py 与官方文档 图的遍历，给出样例图的完整手工推演、复杂度分析与 DFS/BFS 对比。读完后，你将能够独立编写并调试基于邻接表与递归栈的图 DFS 遍历，并理解每一步递归开启与回溯的时机。

这份文档的本质：一个编码了完整程序的教学可视化链接

codes/pythontutor/chapter_graph/graph_dfs.md 与目录下其他文件（如 graph_bfs.md、graph_adjacency_list.md）采用相同的组织形式：文件内容是一条指向 Pythontutor 渲染页面的 URL，URL 的 code= 参数中经过 URL 编码后携带了一份完整可独立运行的 Python 程序，文件头部注释 <!-- [file]{graph_dfs}-[class]{}-[func]{graph_dfs} --> 标注了该程序对应的源文件与目标函数。URL 中的其他查询参数同样携带教学信息：

• py=311：指定解释器为 Python 3.11；
• curInstr=130：预定位到第 130 条指令，即打开页面后已处于 DFS 递归深入阶段的某一步，方便学习者从关键处开始单步执行；
• mode=display、heapPrimitives=nevernest：控制内存堆的展示方式，避免嵌套结构刷屏。

Pythontutor 的定位是把这份代码"动画化"：可以逐条指令单步执行，观察每次 dfs 递归调用时调用栈、visited 集合与 res 列表的变化。下面先把链接中编码的完整程序还原出来。

还原的完整程序：顶点、邻接表图与 DFS

解码 code= 参数后，程序由四个部分组成：顶点类 Vertex、辅助函数 vals_to_vets、基于邻接表的无向图类 GraphAdjList、以及 DFS 本体（入口函数 graph_dfs + 递归辅助函数 dfs）。

class Vertex:
    """顶点类"""
    def __init__(self, val: int):
        self.val = val

def vals_to_vets(vals: list[int]) -> list["Vertex"]:
    """输入值列表 vals ，返回顶点列表 vets"""
    return [Vertex(val) for val in vals]

class GraphAdjList:
    """基于邻接表实现的无向图类"""

    def __init__(self, edges: list[list[Vertex]]):
        """构造方法"""
        self.adj_list = dict[Vertex, list[Vertex]]()
        for edge in edges:
            self.add_vertex(edge[0])
            self.add_vertex(edge[1])
            self.add_edge(edge[0], edge[1])

    def add_edge(self, vet1: Vertex, vet2: Vertex):
        """添加边"""
        if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2:
            raise ValueError()
        self.adj_list[vet1].append(vet2)
        self.adj_list[vet2].append(vet1)

    def add_vertex(self, vet: Vertex):
        """添加顶点"""
        if vet in self.adj_list:
            return
        self.adj_list[vet] = []


def dfs(graph: GraphAdjList, visited: set[Vertex], res: list[Vertex], vet: Vertex):
    """深度优先遍历辅助函数"""
    res.append(vet)        # 记录访问顶点
    visited.add(vet)       # 标记该顶点已被访问
    # 遍历该顶点的所有邻接顶点
    for adjVet in graph.adj_list[vet]:
        if adjVet in visited:
            continue      # 跳过已被访问的顶点
        # 递归访问邻接顶点
        dfs(graph, visited, res, adjVet)


def graph_dfs(graph: GraphAdjList, start_vet: Vertex) -> list[Vertex]:
    """深度优先遍历"""
    # 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
    # 顶点遍历序列
    res = []
    # 哈希集合，用于记录已被访问过的顶点
    visited = set[Vertex]()
    dfs(graph, visited, res, start_vet)
    return res


"""Driver Code"""
if __name__ == "__main__":
    # 初始化无向图
    v = vals_to_vets([0, 1, 2, 3, 4])
    edges = [
        [v[0], v[1]],
        [v[0], v[3]],
        [v[1], v[2]],
        [v[1], v[4]],
        [v[3], v[4]],
    ]
    graph = GraphAdjList(edges)

    # 深度优先遍历
    res = graph_dfs(graph, v[0])

数据结构：为什么 DFS 依赖邻接表

GraphAdjList 用 dict[Vertex, list[Vertex]] 存储邻接表：键是顶点，值是该顶点的全部邻接顶点。构造方法对每条边先执行两次 add_vertex（不存在才建空链表）再执行 add_edge。由于是无向图，add_edge 会在两个顶点的链表中各追加一次对方（adj_list[vet1].append(vet2) 与 adj_list[vet2].append(vet1)），因此每条边在邻接表中被存储两次——这一点直接决定了后文复杂度分析里的 $O(2|E|)$ 项。

DFS 对数据结构的核心诉求是"给定一个顶点，快速取出它的所有邻接顶点"。从源码结构看，dfs 函数中唯一的图访问语句就是 for adjVet in graph.adj_list[vet]，O(1) 取链表、O(度数) 遍历，这正是选择邻接表而非邻接矩阵的原因。仓库中 graph_adjacency_list.py 的 GraphAdjList 与此处为同一实现的完整版本（额外提供了 size、remove_edge、remove_vertex、print 等方法），而顶点定义与 vertex.py 中导出的 Vertex、vals_to_vets、vets_to_vals 完全一致——Vertex 只含一个 val 字段，因此 Python 默认的按值相等语义使它能直接作为哈希集合的键，visited 中 adjVet in visited 的判断即为 O(1)。

递归辅助函数 dfs 的三条核心语句

dfs 函数只有四行有效代码，却覆盖了 DFS 的全部逻辑：

1. 记录访问：res.append(vet) 把当前顶点追加进遍历序列，visited.add(vet) 同步打标。两者必须在递归分叉前完成，否则同一条边从两端各看一次时，邻接顶点会被重复访问；
2. 枚举邻接顶点：for adjVet in graph.adj_list[vet] 沿邻接表向外探索；
3. 剪枝与递归：if adjVet in visited: continue 跳过已访问顶点，这是防止在含环的图上无限递归的关键；对未访问顶点发起 dfs(graph, visited, res, adjVet)，即"优先走到底"。

注意 visited 与 res 都以参数形式传入而非全局变量：在 Python 中，集合和列表是可变对象，函数内部对它们的 add/append 修改会作用于同一对象，因此无需 return 即可把状态带回所有递归层。这也是为什么入口函数 graph_dfs 在调用 dfs 后能直接 return res 拿到完整序列。

入口函数 graph_dfs 则只承担初始化职责：创建空的遍历序列 res 和空的访问集合 visited，然后从 start_vet 出发触发第一次递归。

在样例图上手工推演整个 DFS 过程

样例图有 5 个顶点 0~4 和 5 条边 (0,1) (0,3) (1,2) (1,4) (3,4)，构造出的邻接表为：

0: [1, 3]
1: [0, 2, 4]
2: [1]
3: [0, 4]
4: [1, 3]

以 v[0] 为起点执行 graph_dfs，逐层展开递归栈（缩进表示调用深度，"返回"表示该层 for 循环走完、递归方法返回，即回溯）：

dfs(0)  res=[0]        visited={0}
└─ 邻接 [1, 3]
   dfs(1)  res=[0, 1]  visited={0, 1}
   └─ 邻接 [0, 2, 4]
      0 已访问 → 跳过
      dfs(2)  res=[0, 1, 2]  visited={0, 1, 2}
      └─ 邻接 [1]：1 已访问，循环结束 → 返回
      dfs(4)  res=[0, 1, 2, 4]  visited={0, 1, 2, 4}
      └─ 邻接 [1, 3]
         1 已访问 → 跳过
         dfs(3)  res=[0, 1, 2, 4, 3]  visited={0, 1, 2, 3, 4}
         └─ 邻接 [0, 4] 均已访问，循环结束 → 返回
      循环结束 → 返回
   循环结束 → 返回
循环结束 → 返回

最终返回序列为 [0, 1, 2, 4, 3]。这条推演体现了官方文档 图的遍历 对 DFS 流程图的两种箭头语义：进入 dfs(1)、dfs(2) 等是"向下递推"（开启新的递归方法），dfs(2) 返回到 dfs(1) 的 for 循环中则是"向上回溯"（回到开启此方法的位置）。用 Pythontutor 单步执行时，可以逐帧对照这个调用栈的展开与收缩。

仓库标准实现 graph_dfs.py 的算法部分与上述程序逐行一致，区别仅在驱动代码：它复用了 modules 包中的公共顶点工具，并改用一张 7 顶点、6 条边的图（边为 (0,1) (0,3) (1,2) (2,5) (4,5) (5,6)）演示从 v[0] 出发的 DFS，最后通过 vets_to_vals(res) 把顶点序列转回数值打印。该文件可以直接运行：

python3 codes/python/chapter_graph/graph_dfs.py

它会先打印初始化后的邻接表，再打印深度优先遍历的顶点序列。

DFS 序列为何不唯一，以及复杂度结论

官方文档在 DFS 一节给出了两个值得注意的结论：

• 遍历序列不唯一：与 BFS 相同，DFS 只要求"优先走到底"，给定某顶点时先探索哪个邻接方向都可以——邻接顶点顺序任意打乱后得到的仍是合法的深度优先序列。推演中 dfs(0) 若先访问 3 而不是 1，将得到完全不同的序列但同样正确。以树的遍历为例，前序、中序、后序对应三种不同的访问优先级，却都属于深度优先遍历；
• 时间复杂度：每个顶点恰好被访问 1 次，共 $O(|V|)$；无向图的每条边在邻接表中出现 2 次，因此所有邻接边合计被检查 $O(2|E|)$ 次；总体为 $O(|V| + |E|)$；
• 空间复杂度：res 与 visited 最多各存 $|V|$ 个顶点，递归调用栈深度最大为 $|V|$（一条链状图会递归到最深处），总体 $O(|V|)$。这里递归栈是 DFS 相比 BFS 特有的额外开销来源。

与 BFS 实现的对照

同目录的 graph_bfs.md 内嵌了同构的 BFS 版本（对应仓库文件 graph_bfs.py），两者放在一起恰好勾勒出两种遍历范式的最小差异：

维度	DFS（本文）	BFS
探索策略	一条路走到底再回头，递归实现	由近及远逐层扩张，deque 队列实现
待访问容器	函数调用栈（隐式）	显式队列 que
打标时机	进入顶点时打标（res.append + visited.add 先于枚举邻接点）	入队时打标（que.append 后立即 visited.add），防止同一顶点多次入队
复杂度	$O(	V

小结

这份 Pythontutor 教学文件浓缩了图 DFS 的全部关键要素：邻接表提供 O(1) 的邻接点枚举、visited 哈希集合以 O(1) 查重并阻断含环图上的无限递归、递归调用栈天然实现了"走到尽头再回溯"的控制流。理解了 dfs 中"记录—打标—枚举—剪枝—递归"五步，再借助仓库中 graph_dfs.py 的可运行版本与 graph_traversal.md 中"直虚线向下递推、曲虚线向上回溯"的流程图，即可把单步可视化中的每一帧状态与代码逐行对应起来，并顺理成章地迁移到图的更多应用（连通性判定、路径搜索等）中去。