图算法学习路线复盘BFS、DFS、最短路径、拓扑排序的融会贯通一、深度引言与场景痛点图的题每道都像新题图论算法在学习过程中有一个独特的困境每道题看起来都不太一样。二叉树的题有统一的递归模板数组的题有固定的双指针套路。但图的题——题目描述一变你可能完全不知道该用 BFS 还是 DFS该加 visited 数组还是拓扑排序。7 月我集中攻克了图论专题把 BFS、DFS、最短路径、拓扑排序这四个最核心的模块进行了系统复盘。核心发现是图论题的本质不是记解法而是建立问题特征到图模型的映射能力。你首先得能把问题抽象成一张图——节点是什么边代表什么有向还是无向有权还是无权——然后才轮到选算法。二、底层机制与原理深度剖析四种算法的核心数据结构图论算法的差异本质上是用什么数据结构来管理待处理节点的差异。BFS 使用队列。队列的 FIFO 特性天然保证了先被发现的节点先被处理这正好对应了按层遍历的语义。BFS 的另一个重要特性是在无权图中节点第一次被访问时的距离就是最短距离。这是因为队列中的节点按距离递增排列。DFS 使用栈或递归调用栈。栈的 LIFO 特性保证了先深入后回溯。DFS 的递归版本最简洁但在树很深时有栈溢出风险。迭代版本需要手动维护栈和访问状态。Dijkstra 使用优先队列。优先队列保证每次取出的都是当前已知距离最小的节点。这里有一个关键的不变性当节点从优先队列中弹出时它到起点的距离已经是最短的。这个不变性的前提是所有边的权值都非负。拓扑排序使用队列Kahn 算法或 DFS。Kahn 算法基于入度不断将入度为 0 的节点入队并删除它的出边。DFS 的拓扑排序基于后序一个节点在它所有后继都被处理后才被标记为完成逆后序就是拓扑序。三、生产级代码实现与最佳实践四个算法的工程化实现 图论核心算法模板库 每个算法都实现了两种形式简洁版用于快速原型和工程版带完整错误处理 图的表示统一使用邻接表因为它在大多数场景下比邻接矩阵更节省空间 from collections import deque from heapq import heappush, heappop from typing import List, Dict, Tuple, Optional # 模板一BFS无权图最短路径 def bfs_shortest_path( graph: Dict[int, List[int]], start: int, target: int ) - Optional[int]: BFS 求无权图最短路径长度 时间复杂度O(V E)每个节点和边各访问一次 空间复杂度O(V)队列和 visited 集合 为什么 BFS 能找到最短路径因为在无权图中距离 层数 队列保证了第 k 层的所有节点在第 k1 层的节点之前被处理 if start target: return 0 visited {start} # set 比 list 更适合查重O(1) vs O(n) queue deque([(start, 0)]) # (节点, 距离) while queue: node, dist queue.popleft() # popleft() 而非 pop()保证 FIFO for neighbor in graph.get(node, []): if neighbor target: return dist 1 # 第一次遇到 target 时距离即最短 if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, dist 1)) return None # 不可达 # 模板二DFS三色标记环检测 def has_cycle_dfs(graph: Dict[int, List[int]], n: int) - bool: 有向图环检测 —— 三色标记法 时间复杂度O(V E) 空间复杂度O(V) 三种颜色含义 WHITE (0) 未访问 GRAY (1) 正在访问中在当前递归路径上 BLACK (2) 已完成访问 如果在递归路径上遇到 GRAY 节点说明存在后向边即有环 WHITE, GRAY, BLACK 0, 1, 2 color [WHITE] * n def dfs(node: int) - bool: color[node] GRAY # 标记为正在访问 for neighbor in graph.get(node, []): if color[neighbor] GRAY: return True # 发现后向边有环 if color[neighbor] WHITE and dfs(neighbor): return True color[node] BLACK # 当前节点及所有后继处理完毕 return False for i in range(n): if color[i] WHITE: if dfs(i): return True return False # 模板三Dijkstra优先队列优化 def dijkstra( graph: Dict[int, List[Tuple[int, int]]], start: int, n: int ) - List[int]: Dijkstra 最短路径 时间复杂度O((V E) log V)每次堆操作为 log V 空间复杂度O(V) 关键不变式节点从堆中弹出时dist[节点] 已是全局最短 这个不变式依赖所有边权非负这个前提 INF float(inf) dist [INF] * n dist[start] 0 # 优先队列存储 (距离, 节点)按距离排序 heap [(0, start)] while heap: d, u heappop(heap) if d dist[u]: # 旧记录跳过 —— 同一个节点可能有多个距离记录在堆中 continue for v, weight in graph.get(u, []): new_dist d weight if new_dist dist[v]: dist[v] new_dist heappush(heap, (new_dist, v)) return dist # 模板四拓扑排序Kahn 算法 def topological_sort_kahn( graph: Dict[int, List[int]], n: int ) - Optional[List[int]]: Kahn 算法实现拓扑排序 时间复杂度O(V E) 空间复杂度O(V) 核心思想维护每个节点的入度反复取出入度为 0 的节点 如果最终结果长度 n说明图中有环有向无环图才存在拓扑序 indegree [0] * n # 计算每个节点的入度 for u in range(n): for v in graph.get(u, []): indegree[v] 1 queue deque([i for i in range(n) if indegree[i] 0]) result [] while queue: u queue.popleft() result.append(u) for v in graph.get(u, []): indegree[v] - 1 # 移除 u → v 这条边 if indegree[v] 0: queue.append(v) # 入度为 0 的节点加入队列 if len(result) n: return None # 有环不存在拓扑序 return result这四个模板的共同点是都依赖一个待处理集合的数据结构算法的正确性由该数据结构的不变性保证。理解了这一点面对变形题时就能更快定位问题出在哪里。四、边界分析与架构权衡何时应该把问题建模成图不是所有问题都适合用图论算法。建模成图的代价是引入额外的抽象层有时反而降低了代码的可读性和执行效率。以下三个条件同时满足时才应该考虑图建模第一元素间存在显式的连接/依赖关系。如果是孤立的元素集合就不用建图。比如两数之和不需要图但课程表先修课程依赖天然就是图。第二需要处理到达/连通/顺序等问题。图的核心能力是表达从 A 到 B的关系。如果问题不涉及这个语义建图是徒增复杂度。第三图的规模在可承受范围内。BFS/DFS 可以处理百万级节点但 Floyd-Warshall 的 O(V³) 在 V 500 时就很吃力了。建模前先估算图规模。另一个重要决策是邻接表 vs 邻接矩阵。邻接矩阵适合稠密图E ≈ V²O(1) 判断邻接但空间 O(V²)。邻接表适合稀疏图现实中的大多数图空间 O(V E)遍历邻居快。默认用邻接表除非明确知道图很稠密。五、总结图论的学习路径不是从 BFS 到 Dijkstra 的线性排列而是从图的建模能力到算法选型能力的二维矩阵。你首先要能把问题抽象成图其次是能快速判断该用哪种图算法。7 月的复盘让我确认了一个规律图论题看着杂其实归纳下来就是节点 边 遍历策略三个维度。节点定义清楚了边定义清楚了遍历策略BFS/DFS/Dijkstra/Kahn就是对号入座的事。8 月继续攻最小生成树和网络流。图论是道硬菜但只要框架对了后面都是加调料。