Algorithm · Graph
关系的数学：BFS/DFS · 拓扑排序 · 二分图 · Dijkstra 与 MST —— 依赖调度、社交网络、地图路由的底层引擎
BFS 管层次/无权最短，DFS 管结构/连通——两大遍历撑起一半图题
拓扑排序管依赖调度；染色法管二分图判定
Dijkstra（非负最短路）· Bellman-Ford（负权/负环）· Kruskal/Prim（MST）
Why Graph Algorithms
| 现实问题 | 抽象成图 | 换来的能力 |
|---|---|---|
| 100 个模块，先编译哪个 | 节点 = 模块，边 = 依赖关系 | 拓扑排序 O(V+E) 一次排好，还顺带告诉你有没有循环依赖 |
| 地图上 A 到 B 最快怎么走 | 节点 = 路口，边 = 路段（带通行时间） | Dijkstra 一次算出 A 到所有点的最短路 |
| 一张图里有多少块连通的陆地 | 格子 = 节点，相邻 = 边 | 一次 DFS 数出连通块个数 |
三个任务 A、B、C：A 要在 B 之后做、B 要在 C 之后做 → 顺序自然是 C → B → A。现在再加一条"C 要在 A 之后做"——没有任何顺序可行，你撞上了循环依赖。这两件事（排出顺序 + 发现排不出来）就是拓扑排序的全部。
三个任务你自己排得出来，一百个任务呢？人脑一次最多追踪几条依赖链，而图算法处理一千个节点也是 O(V+E) 毫秒级。这不是"快一点"，是从"做不到"变成"做得到"。
社交网络的"几度好友"、路由器之间的选路、推荐系统里的物品关系、编译器的依赖分析、数据库的外键拓扑——背后全都是同一套遍历与最短路。学会图的建模，比背十个模板更有价值。
先讲"边怎么存"（下一页）→ 两大遍历 BFS/DFS → 网格图 → 拓扑排序与二分图 → 加权图三把钥匙（Dijkstra / Bellman-Ford / Floyd）→ 最小生成树。
Prerequisites & Glossary
| 术语 | 一句话理解（先记住这个，细节后面展开） |
|---|---|
| 顶点 / 节点 vertex | 被研究的那个东西：一个模块、一个路口、一个用户 |
| 边 edge | 两个节点之间的关系。无向边双向通行（好友关系），有向边单向（依赖、关注） |
| 权 weight | 边上的数字：距离、耗时、代价。有权图和无权图解法完全不同 |
| 度 / 入度 / 出度 | 无向图度=邻居数；有向图分入度（指向我的边数）与出度。入度是拓扑排序的核心信号 |
| 邻接表 / 邻接矩阵 | 存边的两种方式：表省空间适合稀疏图，矩阵查边 O(1) 适合稠密图 |
| 路径 / 最短路径 | 沿边走出来的一串节点；最短按"边的条数"（无权）或"权的总和"（带权）度量 |
| 环 cycle | 能从某点出发沿边走回自己。有环就没法拓扑排序（依赖成死结） |
| DAG | 有向无环图（Directed Acyclic Graph）。拓扑排序与 DP on DAG 的地盘 |
| 连通分量 | 互相可达的节点聚成的一团；不连通的图要分几团分别处理，否则会漏算 |
| 松弛 relaxation | 最短路里的核心动作：如果发现更近的走法，就把距离改小——所有最短路算法都在反复做这件事 |
先读这几篇再回来。本 deck 默认你已经能读懂数组、递归和队列：
栈与队列 → BFS 的队列、DFS 的栈
堆与优先队列 → Dijkstra 与 Prim 的标配外设
并查集 → Kruskal 与动态连通的引擎
复杂度分析 → O(V+E) 这些账怎么算
把图算法记成一个固定动作：先把"东西"写成节点、"东西之间的关系"写成边，然后从某个起点出发，沿着边一步一步走，走到哪就处理到哪。后面所有算法的差别只在三件事：① 用什么容器决定"下一步走哪"（队列 / 栈 / 堆）；② 走的时候记什么（距离 / 颜色 / 时间戳）；③ 什么时候停。
它是三把最短路钥匙（Dijkstra / Bellman-Ford / Floyd）唯一的共同动作：发现更近的走法就把距离改小。三个算法的差别只是"以什么顺序反复做这个动作"。把这层看穿，最短路就不再需要背三份代码。
Adjacency List vs Matrix
上一页说"把东西写成节点、关系写成边"——这一页讲这些边具体怎么存。存法选错，后面每个算法的常数都会吃亏。
// 邻接表（Go 习惯：map 或切片数组） graph := make([][]int, n) graph[u] = append(graph[u], v) // 带权图：存 (to, w) 对 type Edge struct{ to, w int } g := make([][]Edge, n) g[u] = append(g[u], Edge{v, w}) // 邻接矩阵：稠密图 / O(1) 查边 mat := make([][]int, n) // n×n mat[u][v] = w
表：空间 O(V+E)，遍历邻居 O(deg)，查边 O(deg)——稀疏图默认选择（真实系统 E≪V²）。矩阵：空间 O(V²)，查边/加边 O(1)——稠密图、Floyd、快速判边时用。
边列表（Kruskal 的输入形态）、CSR 压缩（工业图引擎）、隐式图（棋盘/状态空间不显式建图，直接在坐标上走）。
无向图度 = 邻居数；有向图分入度/出度——入度是拓扑排序的核心信号（下一页）。度数序列、握手定理 Σdeg=2E 是基础自查工具。
有向/无向 · 带权/无权 · 稀疏/稠密 · DAG（拓扑的前提）· 连通/不连通——先分类再套算法，每类算法都有前提（Dijkstra 要非负权、拓扑要 DAG）。
Two Traversals
// BFS：队列 + 层次（无权最短路） func bfs(g [][]int, s int) []int { dist := make([]int, len(g)) for i := range dist { dist[i] = -1 } dist[s] = 0 q := []int{s} for len(q) > 0 { u := q[0]; q = q[1:] for _, v := range g[u] { if dist[v] == -1 { dist[v] = dist[u] + 1 q = append(q, v) } } } return dist } // DFS：递归栈 + 结构信息 func dfs(g [][]int, u int, vis []bool) { vis[u] = true for _, v := range g[u] { if !vis[v] { dfs(g, v, vis) } } }
FIFO 保证先访问的层次浅——无权图最短路径的正确性来源。入队时标记 visited（不是出队时，否则重复入队爆炸）。应用：最短步数、层序、多源 BFS（994 腐烂橘子——把所有源点一起入队）。
递归栈天然给出"当前路径"；进入/离开时间戳可判环（有向图）、求拓扑序、找桥/割点（Tarjan）。应用：连通分量、环检测、拓扑。
都是 O(V+E)；BFS 费内存（队列最宽 O(V)）、DFS 费栈（最深 O(V)，Go 栈可增长）。求最短用 BFS，找结构用 DFS——一句话选型。
对每个未访问点启动一次遍历 → 启动次数 = 分量数；或用并查集（动态加边场景完胜）。
Grid Graph · LC 200/695/130
每个'1'格子是节点，上下左右相邻是边——隐式图，不需要建邻接表，直接在矩阵上走。遍历框架不变，"邻居"换成四个方向向量。
扫每个格子，遇 '1' 启动一次 DFS/BFS 并沉岛（'1'→'0' 原地标记，免 visited 数组）——启动次数即岛数。O(MN) 时间。
695：DFS 返回子树大小求 max；463：不遍历，总周长 = 4·块数 − 2·共享边，纯计数。
反向思维：只从边界上的 O 启动 DFS 标记"不被围的"，剩下全改 X——"从边界反推"是网格题的常用巧劲。
305 岛屿数量 II（逐个加陆地）：静态遍历失效，必须并查集增量维护（并查集 deck）。
| 题 | 问法 | 解法 |
|---|---|---|
| 200 岛屿数量 M | 连通块个数 | 遍历 + 沉岛 |
| 695 最大面积 M | 最大连通块 | DFS 返回子树大小 |
| 463 岛屿周长 E | 边界总长 | 纯计数：4·块数 − 2·共享边 |
| 130 被围区域 M | 保留非边界连通 O | 边界反向 DFS 标记 |
| 305 岛屿 II（会员） | 动态加陆地 | 并查集 |
Topological Sort · LC 207/210
// Kahn 算法：入度表 + 队列 func canFinish(n int, pre [][]int) bool { g := make([][]int, n) indeg := make([]int, n) for _, p := range pre { g[p[1]] = append(g[p[1]], p[0]) indeg[p[0]]++ } q := []int{} for i := 0; i < n; i++ { if indeg[i] == 0 { q = append(q, i) } } done := 0 for len(q) > 0 { u := q[0]; q = q[1:] done++ for _, v := range g[u] { if indeg[v]--; indeg[v] == 0 { q = append(q, v) } } } return done == n // 有环则 < n }
DAG 的线性序：所有边 u→v 都有 u 在 v 前。前提是 DAG——有向有环图没有拓扑序，"能否拓扑排序"="是否有环"。
① Kahn（本页）：入度 0 的进队、出队时削邻居入度——直观、能顺便判环（done < n）；② DFS 逆后序：节点完成时入栈，栈序即拓扑序（回溯/DFS 的副产品）。
207 只问"能否修完"（判环，返回 done==n）；210 要求"输出一个顺序"（记录出队序列）。同一算法，两个返回。
构建系统依赖调度、任务编排（Airflow/DAG 工作流）、包管理器安装顺序、编译单元排序——"先修关系"在工程里的名字叫 DAG 调度。
Bipartite · LC 785/886
节点可分成两组、所有边横跨两组（组内无边）。定理：图是二分图 ⇔ 无奇数环。判定 = 染色法：相邻节点异色， DFS/BFS 染色遇冲突即非二分。
color 数组 0 未染 / 1 / −1；对每个未染分量：起点染 1，DFS 中邻居染相反色；邻居已染色且与当前相同 → 冲突 → false。O(V+E)。
① 可能的二分法（785/886 含 dislikes 约束：把"互相讨厌"建成边，染开两营）；② 任务分配/匹配问题的建模前置（匈牙利算法求最大匹配——面试点到为止）；③ 判定奇环存在性。
二分图沿边走必然两组交替 → 走回起点经过偶数步 → 所有环偶长。反之含奇环染色必冲突。证明一句话能说出来即可。
调度中的"冲突互斥分组"、广告主与流量的二部匹配、编译器寄存器分配的干涉图（读多写少的入门案例）。
| 要点 | 内容 |
|---|---|
| 判定 | 染色法 DFS/BFS，O(V+E) |
| 等价条件 | 无奇数环 |
| 不连通图 | 每个分量独立染色 |
| 进阶 | 匈牙利算法：最大匹配 O(VE)（了解） |
| 变形题 | 886 可能的二分法（约束建边） |
Non-negative Shortest Path · LC 743
// 网络延迟时间（LC 743）：单源最短路 func networkDelayTime(times [][]int, n, k int) int { g := make([][]Edge, n+1) for _, t := range times { g[t[0]] = append(g[t[0]], Edge{t[1], t[2]}) } dist := make([]int, n+1) for i := range dist { dist[i] = 1<<62 } dist[k] = 0 h := &MinHeap{} // (dist, node) heap.Push(h, Item{k, 0}) for h.Len() > 0 { it := heap.Pop(h).(Item) u, d := it.node, it.dist if d > dist[u] { continue } // 惰性删除 for _, e := range g[u] { if nd := d + e.w; nd < dist[e.to] { dist[e.to] = nd heap.Push(h, Item{e.to, nd}) } } } // dist 全可达 → 答案 = max(dist) }
每轮取出当前 dist 最小且未定的节点，它已不可能被绕路改善——这个"锁定"只在边权非负时成立。负权边会让"绕路更短"，贪心失效（→ Bellman-Ford）。
① 惰性删除：同一节点可能多次入堆，弹出时 d > dist[u] 直接跳过——比维护索引堆简单，代价是堆稍大；② 堆版复杂度 O((V+E) log V)，稀疏图远优于朴素 O(V²) 扫描。
多源：所有源点入堆（多源 BFS 的加权版）；终点提前停（target 弹出即返回）；A*：dist + 启发函数 h（有 h≤真实距离保证时仍最优）。
Bellman-Ford · Floyd
对所有边松弛 V−1 轮：第 k 轮结束后"最多 k 条边"的最短路已正确——数学归纳保证。O(V·E)，慢但稳。
第 V 轮还能松弛 → 存在负环（绕一圈更短，最短路无定义）。检测负环是 BF 独有的能力，Dijkstra 做不了。
只松弛"上轮被更新的点"（队列去重）——平均快、最坏仍 O(VE)。竞赛常用，工程负权场景也可用。
dp[k][i][j] = 经由前 k 个点中转的 i→j 最短路：d[i][j] = min(d[i][j], d[i][k]+d[k][j])。本质是"允许中转点集合"的 DP——三维压二维。V≤500 以内的稠密图多源查询直接用它。
单源非负 → Dijkstra；有负权/要检测负环 → Bellman-Ford/SPFA；多源或图很小 → Floyd。先把"单源还是多源、有没有负权"两问答完。
| 算法 | 复杂度 | 负权 | 场景 |
|---|---|---|---|
| BFS | O(V+E) | 仅无权 | 无权最短/步数 |
| Dijkstra + 堆 | O((V+E)logV) | ✗ | 非负权单源默认 |
| Bellman-Ford | O(V·E) | ✓ + 负环检测 | 负权/限制边数（BF 限定 k 轮） |
| SPFA | 均摊快 | ✓ | 竞赛常用 |
| Floyd | O(V³) | ✓（无负环） | 多源/小图/传递闭包 |
MST · Kruskal / Prim
n 个点选 n−1 条边连通且总权最小。贪心可证（切割性质：横跨任意切割的最小边必在某个 MST 里）——两大实现是同一性质的两种用法。
边按权排序，逐条试加：两端不同根（并查集）就选入。O(E log E)——排序主导。实现最简单，稀疏图首选。
从任意点开始，每次取"树外到树内最短的边"扩张——堆维护横切边 O(E log V)。稠密图可用朴素 O(V²) 版。
稀疏图 → Kruskal（排序+并查集，代码短）；稠密图 → Prim（堆版或朴素版）。两者都要求图连通——不连通得到的是最小生成森林。
LC 1584 连接所有点的最小费用（曼哈顿距离建边 + Kruskal）、1135 最低成本联通（会员）。MST 在网络布线、聚类（单链接聚类）里是真实生产算法。
| 维度 | Kruskal | Prim |
|---|---|---|
| 视角 | 边排序逐条试 | 点扩张养树 |
| 数据结构 | 排序 + 并查集 | 堆（横切边） |
| 复杂度 | O(E log E) | O(E log V) |
| 适合 | 稀疏图、边列表输入 | 稠密图、邻接矩阵 |
| 代码量 | 最短 | 中等 |
LeetCode Shortlist
| 专题 | 题目（编号 · 难度） | 要点 |
|---|---|---|
| 遍历/岛屿 | 200 岛屿 M · 695 面积 M · 130 被围区域 M · 994 腐烂橘子 M | 994 是多源 BFS 标准题 |
| 最短步数 | 542 01 矩阵 M · 127 单词接龙 H · 752 打开转盘锁 M | 无权最短 = BFS 全家桶 |
| 拓扑排序 | 207 课程表 M · 210 课程表 II M · 802 找到安全状态 M | Kahn 判环 + 输出序 |
| 二分图/染色 | 785 判断二分图 M · 886 可能的二分法 M | 染色冲突判定 |
| 最短路 | 743 网络延迟 M · 1631 最小体力消耗 M · 787 K 站中转 M | 743 Dijkstra；787 限定轮 BF |
| MST/并查集 | 1584 连接所有点 M · 684 冗余连接 M · 721 账户合并 M | Kruskal + 并查集组合拳 |
Cheat Sheet
| 先问 | 答案决定你用谁 |
|---|---|
| 边有没有权？ | 无权 → BFS（层数是步数）；带权 → Dijkstra / Bellman-Ford / Floyd |
| 单源还是多源？ | 单源 → BFS / Dijkstra / BF；多源 → Floyd，或把所有源点一起入队的多源 BFS / Dijkstra |
| 权里有没有负数？ | 有 → Bellman-Ford（还顺带能检负环）；没有 → Dijkstra |
| 算法 | 解决什么 | 复杂度 | 前提 |
|---|---|---|---|
| BFS | 无权最短路 / 最少步数 | O(V+E) | 边无权 |
| 拓扑排序 | 依赖排序 + 判环 | O(V+E) | 必须是 DAG |
| DFS 染色 | 二分图判定 | O(V+E) | — |
| Dijkstra + 堆 | 非负权单源最短路 | O((V+E)logV) | 边权非负 |
| Bellman-Ford | 负权最短路 + 负环检测 | O(V·E) | — |
| Floyd | 多源最短路 | O(V³) | 无负环 |
| Kruskal / Prim | 最小生成树 | O(E log E) / O(E log V) | 图连通 |
| 维度 | BFS | DFS |
|---|---|---|
| 容器 | 队列（FIFO） | 栈 / 递归 |
| 拿到的是 | 层次——无权最短路 | 结构——路径与时间戳 |
| visited 时机 | 入队时标记 | 进入时标记 |
| 选型一句话 | 求最短用 BFS | 找结构用 DFS |
1 · 建图三步走完了吗？数节点数 n（小心 1-indexed 输入）、加边、选起点。图题 80% 的 bug 在建图，不在算法。
2 · 有向还是无向？无向图漏加反向边 = 一半的图凭空消失；有向图多加反向边 = 答案全错。
3 · BFS 的 visited 入队时标记了吗？出队时才标记会让同一节点被多个前驱重复入队，队列规模直接爆炸。
4 · 前提满足吗？Dijkstra 要非负权、拓扑要 DAG、MST 要连通——前提不满足不会报错，只会静默给出错答案。
5 · 图连通吗？一次遍历覆盖不到的点要不要再启动一次？连通分量计数题漏了这一步就会少算。
Interview QA · Part 1
先自答，再对照：每题先说出你的答案（哪怕只说关键词），再展开下面那行——卡住的那 30 秒才是真正长记性的部分。
表：空间 O(V+E)、遍历邻居快——稀疏图默认；矩阵：O(V²) 空间、查边 O(1)——稠密图、需要 O(1) 判边（Floyd/传递闭包）时用。
队列 FIFO 保证 k 层节点全部处理完才碰 k+1 层——首次到达某节点时的层数就是最少边数。换成栈（DFS）层次序被破坏，最短性失效。
入队时标记，不是出队时——否则同一节点被多个前驱重复入队，队列规模爆炸。这是 BFS 最经典的实现错误。
所有源点同时入队（dist=0）再扩散——等价于建一个虚拟超级源点连向所有源点。994 腐烂橘子、542 01 矩阵都是它，无需逐源跑 BFS。
Kahn：入度队列，能顺便判环（done<n）、能输出"当前可执行集合"；DFS 逆后序：代码短但要先判环才能用。工程调度（需要知道每步可并行的任务）用 Kahn 更自然。
DFS 三色：白（未访）/灰（递归栈中）/黑（已完成）——遇到灰节点即有环。灰=当前路径，比"visited+inStack 两数组"更统一。
二分图上任意环必在两组间交替 → 环长偶数。染色法遇冲突 ⇔ 存在奇环。判定 O(V+E)，不连通图逐分量染。
把访问过的 '1' 改 '0'，省掉 visited 矩阵 O(MN) 空间。代价是破坏输入——不允许改输入时用 visited 或恢复现场（回溯语义）。
Interview QA · Part 2
先自答，再对照。这一组的重点是"选型"——看到题先自己回答"有没有负权、单源还是多源"，再对照答案。
它把"当前 dist 最小"的节点永久锁定——负权边可能让"绕更多条边反而更短"，锁定的贪心不再成立。Bellman-Ford 不锁定节点，逐轮松弛容忍负权。
同一节点多次松弛会多次入堆；弹出时若 d>dist[u] 说明是过期条目直接跳过。省掉 decrease-key 的复杂实现，堆多占 O(E) 空间——工程上的标准取舍。
最短路最多 V−1 条边；第 k 轮后"≤k 条边"的最短路全部正确（归纳）。第 V 轮仍能松弛 → 有环被反复松弛 → 负环。LC 787 的"限 k 站"就是只用前 k 轮。
dp[k][i][j] = 只经前 k 个点中转的 i→j 最短路；转移：经过 k 与不经过 k 取 min。本质是"允许中转集合"逐步扩大的 DP——空间可压成二维原地更新。
稀疏图 E≈V：Kruskal 排序+并查集，O(E log E)、代码最短；稠密图 E≈V²：Prim 堆版 O(E log V) 或朴素 O(V²)。输入形态（边列表 vs 邻接矩阵）常常替你做了决定。
调度系统=拓扑排序（Airflow DAG）、社交推荐=图的 BFS/连通、地图导航=Dijkstra/A*、网络布线= MST、依赖安装=拓扑 + 环检测报错。面试把算法映射回系统是高级信号。
Related & References
参考来源（本 deck 结论可溯源至下列一手材料）
| CLRS ch22/23/24/25 | 基本图算法 · MST · 单源最短路 · 全源最短路 |
| Dijkstra (1959) · Bellman (1958) · Floyd (1962) | 三大最短路算法原始论文 |
| LeetCode 200/207/785/743/787/1584 官方题解 | 六专题代表题 |
| oi-wiki.org/graph | 图论算法的中文系统讲解（含 SPFA/负环） |
| Airflow/Argo 文档 · DAG 工作流 | 拓扑排序的工程落地佐证 |