企业官网建设流程全解析

图算法核心模式实战：邻接表、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, visited=None): 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）无法区分"正在探索"与"探索完毕"。遇到正在探索的节点（state=1）意味着找到了后向边，即环；遇到已完成节点（state=2）只是跨边，不构成环。

进阶：课程表 II（Course 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 算法三步走：

1. 在原图上 DFS，记录节点完成（出栈）顺序；
2. 转置图（反转所有边的方向）；
3. 按完成顺序的逆序在转置图上 DFS，每棵 DFS 树即一个 SCC。

应用场景：查找循环依赖、2-SAT 问题、将有向图凝聚（condense）为 SCC 的 DAG。课程表问题（Course Schedule）本质是判断"SCC 是否只有单节点"，即无环。

常见陷阱总结

下表汇总了图问题中最容易踩的坑，来自原文档：

连通分量的另一条路：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