图算法核心模式实战邻接表、BFS/DFS、最短路径与拓扑排序 —— Maths, CS AI Compendium 之 Graphs 篇【免费下载链接】maths-cs-ai-compendiumBecome a cracked AI/ML researcher/engineer with this unconventional textbook covering maths, computing, and ML with intuition.项目地址: https://gitcode.com/GitHub_Trending/mat/maths-cs-ai-compendium本指南围绕开源教科书 Maths, CS AI Compendium 的 第 14 章 Graphs 文档 展开系统讲解图的表示方法、BFS/DFS 两大遍历范式、Dijkstra 最短路径、拓扑排序与强连通分量覆盖社交网络、道路导航、课程依赖等真实场景。读完本文你将掌握面试与工程中最常用的图算法模式如何用队列实现按层遍历、用三色状态检测有向环、用堆实现非负权重最短路并能直接复跑文中的全部 Python 示例。图的数学与工程定位在开始编码之前先厘清图在本书知识体系中的位置本书第 12 章 图论基础 已讲解节点、边、邻接矩阵、图的 Laplacian 与谱理论等数学语言第 13 章 离散数学 则覆盖了树、平面性、图着色、欧拉/哈密顿路径等结构性质。本文聚焦的是算法模式如何在代码中遍历、搜索、优化图结构即用代码解决图问题的那一部分。值得强调的是几乎所有图问题都可以归结为 BFS 或 DFS 两种基础算法可能带修改。掌握这两个范式就能解决绝大多数图问题——无论是 LeetCode / NeetCode 风格的面试图还是推荐系统、路径规划、依赖解析等工程场景。第 14 章的 算法基础文档 强调以模式而非记忆取胜识别问题背后的结构特征本题是图、是树、还是隐式图再套用对应的遍历范式。图的表示邻接表与邻接矩阵邻接表Adjacency List对每个节点存储其邻居列表空间复杂度为 $O(|V| |E|)$最适合稀疏图——而真实世界中的图社交网络、道路网、知识图谱绝大多数是稀疏的。# 无向图 graph { 0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2] } # 从边列表构建 def build_graph(n, edges): graph {i: [] for i in range(n)} for u, v in edges: graph[u].append(v) graph[v].append(u) # 有向图则省略这一行 return graph注意build_graph中的关键决策无向图需要双向添加边有向图只加单向。这是图构建阶段最常见的错误来源见文末陷阱表。邻接矩阵Adjacency Matrix$n \times n$ 矩阵$A[i][j] 1$ 表示边 $(i, j)$ 存在空间复杂度 $O(|V|^2)$。邻接矩阵与图论中谱方法关系密切第 12 章 图论基础 展示了三角形图的邻接矩阵表达并指出 $A^k_{ij}$ 统计节点 $i$ 到 $j$ 之间长度为 $k$ 的路径数——这正是矩阵幂在图上的组合学含义。如何选择邻接表几乎总是首选稀疏图的内存与遍历效率最优。邻接矩阵仅在图很稠密$|E| \approx |V|^2$或需要 $O(1)$ 边存在性查询时使用。第 13 章 离散数学 还提到平面图满足 $|E| \leq 3|V| - 6$由欧拉公式导出因此平面图天然稀疏——这印证了真实图大多稀疏、邻接表够用的结论。模式BFS广度优先搜索BFS 使用队列逐层探索节点适用于无权图的最短路径层序遍历连通分量查找一切最少步数类问题from collections import deque def bfs(graph, start): visited {start} queue deque([start]) while queue: node queue.popleft() for neighbour in graph[node]: if neighbour not in visited: visited.add(neighbour) queue.append(neighbour)关键点必须在入队时标记 visited而非出队时。如果出队时才标记同一节点可能被多个前驱节点重复入队浪费时间甚至导致结果错误。这是 BFS 的第一大陷阱。BFS 的按层传播思想在深度学习领域同样无处不在第 12 章 图神经网络 中的消息传递机制正是每经过一层消息传递节点表示融合其 $k$ 跳邻域信息——BFS 从 1 跳到 2 跳再到 $k$ 跳的扩散过程与 GNN 感受野的扩张如出一辙。理解了 BFS就能理解 GNN 为什么层数越多看到的范围越广。入门岛屿数量Number of Islands问题给定二维网格1 表示陆地0 表示水统计岛屿数量。模式遍历网格遇到 1 就启动一次 BFS/DFS 把所有相连的陆地标记为已访问启动 BFS 的次数即岛屿数。from collections import deque def num_islands(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) count 0 for r in range(rows): for c in range(cols): if grid[r][c] 1: count 1 # BFS 标记整座岛 queue deque([(r, c)]) grid[r][c] 0 # 标记已访问 while queue: cr, cc queue.popleft() for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]: nr, nc cr dr, cc dc if 0 nr rows and 0 nc cols and grid[nr][nc] 1: grid[nr][nc] 0 queue.append((nr, nc)) return count陷阱directions [(0,1),(0,-1),(1,0),(-1,0)]四方向偏移是几乎所有网格题DFS、BFS、DP都要背下的模式8 连通问题只需加上四条对角线。陷阱直接修改输入网格grid[r][c] 0可省去独立 visited 集合面试中可接受但需明确说明这一取舍会修改入参。进阶腐烂的橘子Rotting Oranges问题新鲜橘子会因相邻烂橘子而腐烂返回全部腐烂所需最短时间不可能则返回 -1。模式多源 BFS。把初始所有烂橘子同时放入队列每个 BFS 层级代表一个时间步。from collections import deque def oranges_rotting(grid): rows, cols len(grid), len(grid[0]) queue deque() fresh 0 for r in range(rows): for c in range(cols): if grid[r][c] 2: queue.append((r, c)) elif grid[r][c] 1: fresh 1 if fresh 0: return 0 time 0 while queue and fresh 0: time 1 for _ in range(len(queue)): cr, cc queue.popleft() for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]: nr, nc cr dr, cc dc if 0 nr rows and 0 nc cols and grid[nr][nc] 1: grid[nr][nc] 2 fresh - 1 queue.append((nr, nc)) return time if fresh 0 else -1核心洞见多源 BFS 让所有源头同步扩张得到的是到任意源头的最短距离——这正是最后一个新鲜橘子何时烂掉。同时注意for _ in range(len(queue))固定当前层大小保证每次循环恰好推进一个时间步。别忘了fresh 0的边界提前返回。模式DFS深度优先搜索DFS 沿一条路径尽可能深入回溯后再探索其他分支使用显式栈或递归调用栈实现。适用场景环检测拓扑排序连通分量回溯 / 穷举搜索带约束的路径查找def dfs(graph, node, visitedNone): if visited is None: visited set() visited.add(node) for neighbour in graph[node]: if neighbour not in visited: dfs(graph, neighbour, visited)递归版本简洁优雅但注意 算法基础文档 中提醒的递归栈开销$n$ 层深递归占 $O(n)$ 空间Python 默认递归深度上限为 1000超大图需改显式栈或迭代实现。进阶课程表Course Schedule环检测问题给定 $n$ 门课程及其先修关系判断能否全部修完即依赖图中不存在环。模式在有向图中检测环。DFS 使用三状态未访问 / 探索中在当前 DFS 路径上/ 已完成。def can_finish(num_courses, prerequisites): graph {i: [] for i in range(num_courses)} for course, prereq in prerequisites: graph[course].append(prereq) # 0 未访问, 1 探索中, 2 已完成 state [0] * num_courses def has_cycle(node): if state[node] 1: return True # 后向边 → 有环 if state[node] 2: return False # 已完全探索 state[node] 1 # 标记探索中 for neighbour in graph[node]: if has_cycle(neighbour): return True state[node] 2 # 标记已完成 return False for course in range(num_courses): if has_cycle(course): return False return True为什么需要三状态两状态visited/unvisited无法区分正在探索与探索完毕。遇到正在探索的节点state1意味着找到了后向边即环遇到已完成节点state2只是跨边不构成环。进阶课程表 IICourse Schedule II拓扑排序问题返回一个合法的课程修读顺序拓扑序。模式Kahn 算法基于 BFS从入度为 0 的节点出发处理后将邻居入度减 1重复直到队列为空。from collections import deque def find_order(num_courses, prerequisites): graph {i: [] for i in range(num_courses)} indegree [0] * num_courses for course, prereq in prerequisites: graph[prereq].append(course) indegree[course] 1 queue deque([i for i in range(num_courses) if indegree[i] 0]) order [] while queue: node queue.popleft() order.append(node) for neighbour in graph[node]: indegree[neighbour] - 1 if indegree[neighbour] 0: queue.append(neighbour) return order if len(order) num_courses else [] # 结果不足 存在环陷阱若结果节点数少于图节点数说明存在环某些节点入度永远无法降到 0。注意这里建图方向与 Course Schedule 相反graph[prereq].append(course)因为拓扑序要求先修在前。拓扑排序的工程价值远超课程安排第 13 章 操作系统 中的编译依赖、构建系统任务调度、DAG 化流水线本质都是拓扑排序的应用。最短路径Dijkstra 算法在非负权加权图中求单源最短路径核心数据结构是优先队列最小堆。import heapq def dijkstra(graph, start): # graph: {node: [(neighbour, weight), ...]} dist {node: float(inf) for node in graph} dist[start] 0 heap [(0, start)] while heap: d, node heapq.heappop(heap) if d dist[node]: continue # 过期条目跳过 for neighbour, weight in graph[node]: new_dist d weight if new_dist dist[neighbour]: dist[neighbour] new_dist heapq.heappush(heap, (new_dist, neighbour)) return dist时间复杂度使用二叉堆为 $O((|V| |E|) \log |V|)$。陷阱if d dist[node]: continue必不可少。没有它堆中过期条目会被重复处理最坏退化到 $O(|V|^2)$。陷阱Dijkstra 不适用于负权边。一旦有负权边节点被定稿后距离即最优的贪心假设失效应改用 Bellman-Ford。困难网络延迟时间Network Delay Time问题给定 $n$ 个节点和带权有向边求信号从源点到达所有节点的耗时若有节点不可达则返回 -1。def network_delay(times, n, k): graph {i: [] for i in range(1, n 1)} for u, v, w in times: graph[u].append((v, w)) dist dijkstra(graph, k) max_time max(dist.values()) return max_time if max_time float(inf) else -1解法直接把 Dijkstra 封装复用最远可达节点的距离即总延迟存在float(inf)说明有节点不可达。这个先用模板再套题目语义的思路正是第 14 章全书提倡的模式复用。Dijkstra 的贪心扩张与 BFS 一脉相承第 12 章 图论基础 指出 Dijkstra 在 $O((|V| |E|) \log |V|)$ 内求最短路而无权图用 BFS 即可在 $O(|V| |E|)$ 内完成——边权为 1 时 BFS 就是 Dijkstra 的特例。道路导航、自监督学习中的图传播、通信网络路由都建立在这一算法之上。强连通分量SCC在有向图中强连通分量SCC是极大节点集合其中任意两点互相可达。Kosaraju 算法三步走在原图上 DFS记录节点完成出栈顺序转置图反转所有边的方向按完成顺序的逆序在转置图上 DFS每棵 DFS 树即一个 SCC。应用场景查找循环依赖、2-SAT 问题、将有向图凝聚condense为 SCC 的 DAG。课程表问题Course Schedule本质是判断SCC 是否只有单节点即无环。常见陷阱总结下表汇总了图问题中最容易踩的坑来自原文档陷阱示例修复出队时才标记 visited同一节点被多次入队入队时立即标记有向图只用两状态 visited无法区分后向边与跨边用三状态未访问/探索中/已完成Dijkstra 用于负权边最短路结果错误改用 Bellman-Ford忘记if d dist[node]: continue反复处理过期堆条目当前距离更差时直接跳过网格边界检查缺失索引越界0 nr rows and 0 nc cols漏掉 time0 边界腐烂橘子无新鲜橘子时出错BFS 前先检查fresh 0有向图建成无向图先修关系方向错误只按一个方向加边连通分量的另一条路Union-Find本文用 BFS/DFS 求连通分量但第 14 章 树与 Union-Find 提供了等价的替代方案Union-Find并查集通过find路径压缩与union按秩合并两个操作维护不相交集合均摊复杂度 $O(\alpha(n)) \approx O(1)$。对图中有多少个连通分量加边后是否成环如 Redundant Connection类问题并查集通常比反复 DFS 更简洁高效——选择哪种取决于问题是否需要遍历顺序信息。课后练习清单原文档末尾附带的练习问题NeetCode 平台按模式分类供自测BFS 模式岛屿数量网格 BFS/DFS、腐烂的橘子多源 BFS、克隆图BFS 哈希表、太平洋大西洋水流从两个海洋分别 BFS、单词接龙隐式图 BFS。DFS 模式岛屿最大面积DFS 计数、课程表有向图环检测、课程表 II拓扑排序、连通分量数量DFS 或 Union-Find、图是否有效树连通且无环。最短路径网络延迟时间Dijkstra、K 站中转最便宜航班带约束的 BFS/Bellman-Ford、上涨的水中游泳二分 BFS 或网格上的 Dijkstra。进阶外星词典从字符序构建拓扑序。小结图算法没有门派之分本质上只有两条主线BFS 管最少步数/按层扩散DFS 管深入/回溯/环检测再加上Dijkstra非负权最短路与Kahn/Kosaraju拓扑序/SCC两个成熟扩展。先把文中的核心模板跑通再结合 第 12 章图论 的数学视角与 第 14 章算法基础 的复杂度框架遇到新题时剥离故事、识别模式、套用模板就足以覆盖绝大多数图问题。【免费下载链接】maths-cs-ai-compendiumBecome a cracked AI/ML researcher/engineer with this unconventional textbook covering maths, computing, and ML with intuition.项目地址: https://gitcode.com/GitHub_Trending/mat/maths-cs-ai-compendium创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考