图
2026/4/10大约 13 分钟常用算法题图
本章题海战术
图
📌 图的基础存储（面试必问前置）
图的存储是所有算法的基础，面试高频对比两种实现方式：
| 存储方式 | 空间复杂度 | 适用场景 | 增删边效率 | 遍历效率 |
|---|---|---|---|---|
| 邻接矩阵 | O(V²) | 稠密图（边多） | O(1) | 遍历所有边 O (V²) |
| 邻接表 | O(V+E) | 稀疏图（边少，面试 90% 场景） | O(1) | 遍历所有边 O (V+E) |
面试结论：绝大多数算法题优先用邻接表，空间更优。
示例图结构
🚶 最高频基础：图的遍历（DFS/BFS）
所有图论题的底层能力，100% 会结合场景考察。
1. BFS（广度优先遍历）
- 核心思路：队列实现，层序扩散，入队即标记访问
- 适用场景：无权图最短路径、层序遍历、连通性判断
- 时间复杂度：O(V+E)
- 核心代码（Java 模板）
// BFS 通用模板
public void bfs(int start, List<List<Integer>> adj) {
boolean[] visited = new boolean[adj.size()];
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true; // ✅ 技术亮点：入队即标记，避免重复入队导致空间爆炸
while (!queue.isEmpty()) {
int cur = queue.poll();
// 业务逻辑处理当前节点
for (int next : adj.get(cur)) {
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}
}
}
}2. DFS（深度优先遍历）
- 核心思路：递归 / 手动栈实现，一路走到底再回溯
- 适用场景：连通分量统计、路径搜索、环检测、二分图判定
- 时间复杂度：O(V+E)
- 核心代码（迭代版，避免递归栈溢出）
// 迭代式DFS 防栈溢出版本
public void dfs(int start, List<List<Integer>> adj) {
boolean[] visited = new boolean[adj.size()];
Deque<Integer> stack = new ArrayDeque<>();
stack.push(start);
while (!stack.isEmpty()) {
int cur = stack.pop();
if (visited[cur]) continue;
visited[cur] = true;
// 业务逻辑处理当前节点
for (int next : adj.get(cur)) {
if (!visited[next]) stack.push(next);
}
}
}高频应用题：岛屿数量(leetcode 200)、克隆图(leetcode 133)、被围绕的区域(leetcode 130)、二分图判定(leetcode 785)
🔗 高频应用题：拓扑排序
面试考频 Top1 的图论应用题，几乎逢图必考。
- 核心前提：仅适用于有向无环图（DAG）
- 适用场景：依赖调度（课程安排、编译顺序、任务排序）
- 主流实现：Kahn 算法（入度表 + BFS，面试首选写法）
- 时间复杂度：O(V+E)
- 核心代码
// Kahn 拓扑排序算法
public List<Integer> topologicalSort(int n, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
int[] inDegree = new int[n];
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
// 构建邻接表 + 入度数组
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
inDegree[e[1]]++;
}
Queue<Integer> queue = new LinkedList<>();
// 入度为0的节点入队
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) queue.offer(i);
}
List<Integer> res = new ArrayList<>();
while (!queue.isEmpty()) {
int cur = queue.poll();
res.add(cur);
// 邻接点入度-1，入度为0则入队
for (int next : adj.get(cur)) {
inDegree[next]--;
if (inDegree[next] == 0) queue.offer(next);
}
}
// ✅ 技术亮点：自带环检测，结果长度不等于n则存在环
return res.size() == n ? res : new ArrayList<>();
}📐 核心考点：最短路径算法
带权有向示例图
1. Dijkstra 算法（最高频）
- 核心思路：贪心思想，每次选距离起点最近的节点，松弛其邻边
- 适用场景：无负权边的单源最短路径
- 优化版本：优先队列（小顶堆）优化，面试必写优化版
- 时间复杂度：朴素版 O (V²)，优先队列版 O (E log V)
- 核心代码（优先队列优化版）
// Dijkstra 优先队列优化版
public int[] dijkstra(int n, int[][] edges, int start) {
// 邻接表：每个元素存 [邻接点, 边权]
List<int[]>[] adj = new List[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
for (int[] e : edges) adj[e[0]].add(new int[]{e[1], e[2]});
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
// 小顶堆：[当前距离, 节点编号]
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0, start});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int d = cur[0], u = cur[1];
// ✅ 技术亮点：跳过已确定最短距离的节点，大幅减少无效计算
if (d > dist[u]) continue;
// 松弛邻边
for (int[] edge : adj[u]) {
int v = edge[0], w = edge[1];
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.offer(new int[]{dist[v], v});
}
}
}
return dist;
}2. 其他最短路径算法（面试次高频）
| 算法 | 适用场景 | 核心特点 |
|---|---|---|
| Bellman-Ford | 存在负权边、检测负环 | 动态规划思想，可限制路径步数 |
| Floyd-Warshall | 多源最短路径、节点数少 | 三重循环动态规划，O (V³) |
🌳 次高频：最小生成树
1. Kruskal 算法（面试首选）
- 核心思路：边按权值从小到大排序，用并查集依次加边，避免成环
- 适用场景：稀疏图（边少节点多）
- 时间复杂度：O (E log E) （主要来自边排序）
- 核心依赖：并查集数据结构
2. Prim 算法
- 核心思路：从起点出发，优先队列选最小权边扩展节点
- 适用场景：稠密图（边多节点少）
- 时间复杂度：优先队列版 O (E log V)
🧩 图论神器：并查集
图论最常用的辅助数据结构，很多算法的核心组件。
- 适用场景：连通性判断、环检测、Kruskal 算法、朋友圈问题
- 技术亮点：路径压缩 + 按秩合并，均摊时间复杂度近乎 O (1)
- 核心代码
// 并查集 标准模板
class UnionFind {
int[] parent;
int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
// 路径压缩
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
// 按秩合并
public boolean union(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return false;
if (rank[fx] < rank[fy]) parent[fx] = fy;
else {
parent[fy] = fx;
if (rank[fx] == rank[fy]) rank[fx]++;
}
return true;
}
}⚠️ 技术难点与解决方案汇总
| 技术难点 | 对应场景 | 解决方案 | 优化效果 |
|---|---|---|---|
| 大图存储空间溢出 | 节点数 > 1e4 的稀疏图误用邻接矩阵 | 改用邻接表存储，仅保存存在的边 | 空间从 O (V²) 降至 O (V+E) |
| DFS 递归栈溢出 | 深度极深的链表型图 | 改用迭代式 DFS，手动栈模拟递归 | 规避 JVM 栈深度限制 |
| Dijkstra 算法超时 | 节点数多的图用朴素版 | 优先队列优化，跳过已确定节点 | 时间从 O (V²) 降至 O (E log V) |
| 负权边结果错误 | 图含负权边误用 Dijkstra | 改用 Bellman-Ford/SPFA 算法 | 支持负权边，同时可检测负环 |
| 拓扑排序环检测 | 依赖关系存在循环 | Kahn 算法判断结果长度是否等于节点数 | 一次遍历同时完成排序 + 环检测 |
| 多源最短路径复杂度过高 | 节点数 > 100 误用 Floyd | 稀疏图改用 V 次 Dijkstra 替代 | 时间从 O (V³) 降至 O (V*E log V) |
收尾（面试话术）
整体来说，图论面试题的核心是题型识别 + 模板套用，高频考点集中在遍历、拓扑排序、最短路径这三类，只要掌握核心模板，再注意边界条件（孤立节点、空图、环检测），基本都能覆盖。
真实面试模拟
真实面试模拟
面试官（平和地）：
同学你好，欢迎参加今天的面试。我们先从基础开始，你能说说“图”这种数据结构，在真实业务里一般怎么抽象和存储吗？
我（候选人）：
😊 好的面试官。图本质上就是节点 + 边，用来表达多对多的关系。
比如社交网络里用户互相关注、地铁站的连通、甚至编译时的任务依赖，都可以建模成图。
存储上我一般用邻接表，空间更省，尤其对于稀疏图。我写个简单的 Java 定义：
public class Graph {
// 邻接表：每个顶点维护一个邻居链表
private final List<List<Integer>> adj;
public Graph(int n) {
adj = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
adj.add(new LinkedList<>());
}
}
// 无向边
public void addEdge(int u, int v) {
adj.get(u).add(v);
adj.get(v).add(u);
}
}如果图特别稠密，偶尔也会用邻接矩阵，但大多数工程场景里邻接表足够了。
面试官：
嗯，基础扎实。那图的遍历是最基本的操作，BFS 和 DFS 你平时怎么选？能现场写一个 BFS 找无权最短路径吗？
我：
没问题。我一般这么记：
| 遍历方式 | 数据结构 | 典型应用 |
|---|---|---|
| BFS | 队列 | 最短路径（无权）、扩散问题 |
| DFS | 栈/递归 | 连通分量、环检测、拓扑排序 |
BFS 标准模板我直接写一下：
public int bfsShortestPath(Graph graph, int start, int target) {
boolean[] visited = new boolean[graph.size()];
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
int step = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int cur = queue.poll();
if (cur == target) return step;
for (int next : graph.getNeighbors(cur)) {
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}
}
}
step++;
}
return -1;
}这个按层遍历的框架在扩散型问题（比如腐烂橘子）里非常常用。
面试官：
不错。那 DFS 呢？给你一个无向图，怎么判断有没有环？写一下核心递归。
我：
好的，我用父节点标记法避免误判回头路：
public boolean hasCycle(Graph graph) {
boolean[] visited = new boolean[graph.size()];
for (int i = 0; i < graph.size(); i++) {
if (!visited[i]) {
if (dfs(graph, i, visited, -1)) return true;
}
}
return false;
}
private boolean dfs(Graph graph, int cur, boolean[] visited, int parent) {
visited[cur] = true;
for (int next : graph.getNeighbors(cur)) {
if (!visited[next]) {
if (dfs(graph, next, visited, cur)) return true;
} else if (next != parent) {
// 访问过且不是父节点 → 有环
return true;
}
}
return false;
}有向图就更适合用三色标记或者拓扑排序来判断环。
面试官：
好，那咱们进入最短路径。Dijkstra 怎么用堆优化？写一下关键代码，并说说复杂度。
我：
Dijkstra 用优先队列（小顶堆）能把时间复杂度从 O(V²) 降到 O((V+E) log V)。
关键点：每次取出距离最小的顶点，松弛其邻居，遇到更优解就更新并入堆。
public int[] dijkstra(int n, int[][] edges, int src) {
// 1. 建图（邻接表，带权重）
List<int[]>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
for (int[] e : edges) {
graph[e[0]].add(new int[]{e[1], e[2]}); // {to, weight}
}
// 2. 距离数组 + 小顶堆
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.offer(new int[]{src, 0});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int u = cur[0], d = cur[1];
if (d > dist[u]) continue; // 懒删除：忽略过期数据
for (int[] neighbor : graph[u]) {
int v = neighbor[0], w = neighbor[1];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.offer(new int[]{v, dist[v]});
}
}
}
return dist;
}这里 if (d > dist[u]) continue; 就是一个技术亮点，避免重复处理同一个顶点的旧纪录，实际工程里能减少很多无效操作。
面试官：
如果图有负权边呢？Dijkstra 还适用吗？
我：
不适用，因为负权边可能让已确定最短路径的顶点又被更新。这时我会改用 Bellman-Ford（适合稀疏负权）或 SPFA（队列优化版）。全源最短路径就用 Johnson 算法。
面试官：
很好。再考一个常见业务场景：任务调度依赖，用拓扑排序解决。写一个 Kahn 算法实现。
我：
拓扑排序我习惯用 BFS + 入度表（Kahn 算法），线性时间，还能顺便检测环：
public int[] topologicalSort(int n, int[][] prerequisites) {
List<Integer>[] adj = new ArrayList[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
int[] inDegree = new int[n];
for (int[] pre : prerequisites) {
adj[pre[1]].add(pre[0]);
inDegree[pre[0]]++;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) q.offer(i);
}
int[] result = new int[n];
int idx = 0;
while (!q.isEmpty()) {
int u = q.poll();
result[idx++] = u;
for (int v : adj[u]) {
if (--inDegree[v] == 0) q.offer(v);
}
}
// 结果数量不足 n → 存在环
return idx == n ? result : new int[0];
}如果结果长度小于 n，就说明图里有环，这种检测在死锁分析里非常实用。
面试官：
最小生成树了解吗？描述一下 Kruskal 并写出带并查集的实现。
我：
Kruskal 核心是贪心 + 并查集判环，适合稀疏图。步骤：边按权重排序 → 依次加入不构成环的边 → 直到选出 n-1 条边。
class UnionFind {
int[] parent;
public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩
return parent[x];
}
public boolean union(int x, int y) {
int rootX = find(x), rootY = find(y);
if (rootX == rootY) return false;
parent[rootX] = rootY;
return true;
}
}
public int kruskalMST(int n, int[][] edges) {
// edges: [u, v, weight]
Arrays.sort(edges, (a, b) -> a[2] - b[2]);
UnionFind uf = new UnionFind(n);
int mstWeight = 0, edgeCount = 0;
for (int[] e : edges) {
if (uf.union(e[0], e[1])) {
mstWeight += e[2];
edgeCount++;
if (edgeCount == n - 1) break;
}
}
return mstWeight;
}并查集的路径压缩是性能亮点，可以近乎 O(1) 完成查找。
面试官：
你在实际项目中遇到过哪些图算法的难点？怎么解决的？
我：
常见痛点我整理了一下：
| 难点 | 典型场景 | 解决思路 |
|---|---|---|
| 图太大，单机内存放不下 | 十亿级社交网络 | 邻接表分片 + 外存，或上 Spark GraphX 分布式计算 |
| 动态图频繁更新 | 实时路况导航 | 增量最短路径算法（Dynamic SSSP），局部更新 |
| 负权边导致 Dijkstra 失效 | 金融套利检测 | 改用 Bellman-Ford 或 Johnson |
| 多约束最短路径 | 带时间窗的配送规划 | 分层图/拆点，将状态（时间、电量等）编码到顶点 |
| 全源最短路径计算量太大 | 推荐系统相似度 | 基于 Landmark 的近似距离估算 |
比如在做物流调度时，我就在顶点里同时编码“节点ID + 已用时间”，把原图展开成多层图，再用 Dijkstra 求符合时间窗的最优路径。
面试官：
最后，能不能用一个图来总结你掌握的图论体系？
我：
可以，我画个思维导图：
基本覆盖了面试常考的图算法，而且每一种我都自己手写过，理解它们的适用场景和边界条件。
面试官：
很好，思路清晰，代码也很扎实。今天就到这里，谢谢你的时间。
我：
谢谢面试官，期待后续交流 ✌️