这份速查表是为两个时刻打造的：技术面试前的最后一小时，以及写代码到一半、你已看清问题的形状却需要确切工具的时候。它刻意做得很紧凑。想了解每个算法背后的完整故事，请点开深入文章的链接；若想有条理地走完全部内容，请从图论学习路线图开始。
全文中，V 是顶点（节点）数，E 是边数。
复杂度主表
最值得背下来的一件事。这些复杂度假设采用标准的高效实现（Dijkstra 和 Prim 用二叉堆，并查集用路径压缩和按秩合并）。
| 算法 | 最适合 | 时间 | 空间 |
|---|---|---|---|
| BFS | 无权图最短路径、层序 | O(V + E) | O(V) |
| DFS | 连通性、环、探索结构 | O(V + E) | O(V) |
| Dijkstra | 最短路径，非负权 | O((V + E) log V) | O(V) |
| Bellman-Ford | 含负权的最短路径 | O(V · E) | O(V) |
| Floyd-Warshall | 所有点对最短路径，小而稠密的图 | O(V³) | O(V²) |
| A* | 启发式最短路径（地图、游戏） | O(E) 通常 | O(V) |
| Kruskal | 最小生成树，稀疏图 | O(E log E) | O(V) |
| Prim | 最小生成树，稠密图 | O((V + E) log V) | O(V) |
| Topological Sort | 按依赖为 DAG 排序 | O(V + E) | O(V) |
| Union-Find | 动态连通性、分组 | O(α(V)) 每次操作 | O(V) |
| Tarjan / Kosaraju | 强连通分量 | O(V + E) | O(V) |
| Edmonds-Karp | 最大流、最小割 | O(V · E²) | O(V + E) |
| 需要真正的代码吗？ 这张表一眼列出 12 个核心。算法手册 收录全部 55 个，每个都配有伪代码和逐步推导的复杂度。 | |||
关于 A* 的说明：它的运行时间完全取决于启发式函数。启发式完美时，它几乎径直走向目标；启发式毫无用处时，它退化为 Dijkstra。并查集中的 α 是反阿克曼函数，对你今生会遇到的任何输入实际上都是一个小常数。每一行背后的推理，参见图算法复杂度指南。
图的表示法
在任何算法之前，你要先选择如何存储图。这一个决定会影响上面每一项复杂度。
| 表示法 | 空间 | 边查询 | 最适合 |
|---|---|---|---|
| 邻接表 | O(V + E) | O(degree) | 稀疏图，默认选择 |
| 邻接矩阵 | O(V²) | O(1) | 稠密图，常数时间查询 |
经验法则：除非图很稠密或你需要常数时间的边检查，否则就用邻接表。二维网格是一种隐式图，每个格子都是一个与其邻居相连的节点，所以你往往根本不需要任何显式表示。
遍历：BFS 与 DFS
其余一切都建立在这两个算法之上。完整比较见BFS vs DFS。
- BFS 使用队列，逐层探索，并能在无权图中找到最短路径。关键词：最短、最少步数、最近、层序。
- DFS 使用栈（通常是递归调用栈），一路深入，非常适合连通性、环检测和回溯。关键词：所有路径、可达性、区域、探索。
最短路径
面试和实践中最常见的一族。正确选择由边权决定。完整深入见读懂最短路径算法。
| 情形 | 使用 | 原因 |
|---|---|---|
| 无权边 | BFS | 第一次到达即为最短路径 |
| 非负权 | Dijkstra | 配最小堆的贪心，在此总是正确 |
| 负权 | Bellman-Ford | 将边松弛 V-1 次，检测负环 |
| 一次求所有点对 | Floyd-Warshall | 三重嵌套循环，代码极短，小图上很棒 |
| 你有启发式 | A* | 被引导向目标的 Dijkstra，见 A* |
经典陷阱：绝不要在含负边的图上跑 Dijkstra。它会过早把某个节点定为最终结果，可能返回错误答案。请改用 Bellman-Ford。
最小生成树
以最低的总边权连接每一个顶点。两种算法都正确；按图的稠密度来选。完整讲解见最小生成树。
- Kruskal：对所有边排序，加入不构成环的最小边，用并查集检测环。在稀疏图上表现出色。
- Prim：让单棵树向外生长，始终加入离开它的最小边，用优先队列。在稠密图上表现出色。
排序与连通性
- 拓扑排序（Kahn 或基于 DFS）：给出一个 DAG 的线性顺序，使每条边都指向前方。它是处理依赖、构建顺序和调度的工具。若存在环则不可能，而这正是你检测环的方式。
- 并查集（不相交集合）：回答"这两个是否在同一组？"，并以近乎常数的时间合并组。它是 Kruskal 和动态连通性问题的支柱。
- 强连通分量（Tarjan 或 Kosaraju）：在有向图中找出每个节点都能到达其余每个节点的极大分组。两者都在
O(V + E)内运行。
这三者在面试中层出不穷。可查看编程面试必备图算法中的套路解析。
网络流
为吞吐量、匹配和瓶颈建模。这里优美的结论是：最大流等于最小割。完整讲解见网络流与最大流最小割定理。
- Ford-Fulkerson：在残量图中沿增广路径反复推流。简单，但其运行时间取决于流值。
- Edmonds-Karp：用 BFS 寻找增广路径的 Ford-Fulkerson，给出与容量无关的干净上界
O(V · E²)。
我该用哪个算法？
使用这份速查表最快的方式：读左列，跳到右列。
| 如果你需要… | 就用 |
|---|---|
| 访问或探索每个节点 | BFS 或 DFS |
| 在无权图中找最短路径 | BFS |
| 在非负权下找最短路径 | Dijkstra |
| 处理负边权 | Bellman-Ford |
| 求所有点对之间的最短路径 | Floyd-Warshall |
| 用启发式找一条快速路径（地图、游戏） | A* |
| 以最小代价连接一切 | Kruskal 或 Prim |
| 按依赖为任务排序 | 拓扑排序 |
| 检查两个节点是否连通，或对元素分组 | Union-Find |
| 在有向图中找出簇 | Tarjan 或 Kosaraju（SCC） |
| 最大化吞吐量或找出瓶颈 | Edmonds-Karp（最大流） |
常见问题
Dijkstra 算法的时间复杂度是多少？
使用二叉堆（优先队列）时，Dijkstra 算法的时间为 O((V + E) log V)，空间为 O(V)。若用简单数组代替堆，则为 O(V 的平方)，在稠密图上可能更快。
最短路径应该用哪个图算法？
这取决于图。无权图用 BFS，非负权用 Dijkstra，有负权时用 Bellman-Ford，所有点对最短路径用 Floyd-Warshall，有好的启发式时（地图和游戏）用 A*。
应该用邻接表还是邻接矩阵？
稀疏图用邻接表：它占用 O(V + E) 空间，是大多数问题的默认选择。稠密图或需要 O(1) 边查询时用邻接矩阵，代价是 O(V 的平方) 空间。
编程面试应该记住哪些图算法？
五个核心是 BFS、DFS、Dijkstra 算法、拓扑排序和并查集。它们合起来覆盖了技术面试中绝大多数图论题。