Hello 算法Python 图深度优先遍历DFS递归实现逐行解析与 Pythontutor 可视化【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本文以 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 渲染页面的 URLURL 的code参数中经过 URL 编码后携带了一份完整可独立运行的 Python 程序文件头部注释!-- [file]{graph_dfs}-[class]{}-[func]{graph_dfs} --标注了该程序对应的源文件与目标函数。URL 中的其他查询参数同样携带教学信息py311指定解释器为 Python 3.11curInstr130预定位到第 130 条指令即打开页面后已处于 DFS 递归深入阶段的某一步方便学习者从关键处开始单步执行modedisplay、heapPrimitivesnevernest控制内存堆的展示方式避免嵌套结构刷屏。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 的全部逻辑记录访问res.append(vet)把当前顶点追加进遍历序列visited.add(vet)同步打标。两者必须在递归分叉前完成否则同一条边从两端各看一次时邻接顶点会被重复访问枚举邻接顶点for adjVet in graph.adj_list[vet]沿邻接表向外探索剪枝与递归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.appendvisited.add先于枚举邻接点入队时打标que.append后立即visited.add防止同一顶点多次入队复杂度$O(VE)$ 时间$O(V)$ 空间$O(VE)$ 时间$O(V)$ 空间小结这份 Pythontutor 教学文件浓缩了图 DFS 的全部关键要素邻接表提供 O(1) 的邻接点枚举、visited哈希集合以 O(1) 查重并阻断含环图上的无限递归、递归调用栈天然实现了走到尽头再回溯的控制流。理解了dfs中记录—打标—枚举—剪枝—递归五步再借助仓库中 graph_dfs.py 的可运行版本与 graph_traversal.md 中直虚线向下递推、曲虚线向上回溯的流程图即可把单步可视化中的每一帧状态与代码逐行对应起来并顺理成章地迁移到图的更多应用连通性判定、路径搜索等中去。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考