面试官最爱问的图算法：从DFS/BFS到Dijkstra，用Java代码实战带你一次搞懂
在技术面试中，图算法是考察候选人基本功和逻辑思维能力的经典题型。无论是大厂校招还是社招，从简单的DFS/BFS遍历到复杂的最短路径问题，都是面试官检验候选人算法素养的试金石。本文将用Java代码实战，带你系统掌握面试中最常出现的五大图算法，并揭示面试官在这些题目背后真正想考察的解题思维。
1. 图的基础表示与核心概念
在深入算法之前，我们需要建立对图数据结构的正确理解。图由顶点(Vertex)和边(Edge)组成，常见表示方式有邻接矩阵和邻接表两种。
邻接矩阵实现（Java版）：
public class Graph { private List<Integer> vertexList; // 顶点集合 private int[][] edges; // 邻接矩阵 private int edgeCount; // 边数统计 public Graph(int vertexNum) { this.vertexList = new ArrayList<>(vertexNum); this.edges = new int[vertexNum][vertexNum]; this.edgeCount = 0; } // 添加顶点 public void addVertex(int v) { vertexList.add(v); } // 添加边（无向图） public void addEdge(int v1, int v2, int weight) { edges[v1][v2] = weight; edges[v2][v1] = weight; edgeCount++; } // 打印邻接矩阵 public void printMatrix() { for (int[] row : edges) { System.out.println(Arrays.toString(row)); } } }面试注意点：
- 邻接矩阵适合稠密图，空间复杂度O(V²)
- 邻接表适合稀疏图，空间复杂度O(V+E)
- 明确图的类型（有向/无向）和边权特性（加权/未加权）
2. 深度优先搜索(DFS)与广度优先搜索(BFS)
2.1 DFS的递归与非递归实现
DFS如同走迷宫时选择一条路走到底，再回溯探索其他路径。面试中常要求比较递归与迭代实现的差异。
递归版DFS：
void dfs(int v, boolean[] visited, int[][] graph) { visited[v] = true; System.out.print(v + " "); for (int i = 0; i < graph.length; i++) { if (graph[v][i] != 0 && !visited[i]) { dfs(i, visited, graph); } } }栈实现的迭代版DFS：
void dfsStack(int start, int[][] graph) { Stack<Integer> stack = new Stack<>(); boolean[] visited = new boolean[graph.length]; stack.push(start); visited[start] = true; while (!stack.isEmpty()) { int v = stack.pop(); System.out.print(v + " "); // 注意邻接点入栈顺序（与递归顺序一致） for (int i = graph.length-1; i >= 0; i--) { if (graph[v][i] != 0 && !visited[i]) { stack.push(i); visited[i] = true; } } } }2.2 BFS的队列实现与应用场景
BFS像水波纹一样层层扩散，适合求解最短路径问题（无权图）。
队列实现BFS：
void bfs(int start, int[][] graph) { Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[graph.length]; queue.offer(start); visited[start] = true; while (!queue.isEmpty()) { int v = queue.poll(); System.out.print(v + " "); for (int i = 0; i < graph.length; i++) { if (graph[v][i] != 0 && !visited[i]) { queue.offer(i); visited[i] = true; } } } }面试常见问题：
- DFS和BFS的时间复杂度都是O(V+E)
- DFS更适合解决连通性问题，BFS适合最短路径问题
- 如何修改BFS记录路径？→ 使用parent数组回溯
3. Dijkstra算法：单源最短路径
Dijkstra算法是面试最高频的图算法之一，核心是贪心策略+优先队列优化。
优先队列优化实现：
void dijkstra(int[][] graph, int src) { int V = graph.length; int[] dist = new int[V]; 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[] curr = pq.poll(); int u = curr[0]; for (int v = 0; v < V; v++) { if (graph[u][v] != 0) { int newDist = dist[u] + graph[u][v]; if (newDist < dist[v]) { dist[v] = newDist; pq.offer(new int[]{v, newDist}); } } } } // 输出最短路径 for (int i = 0; i < V; i++) { System.out.println(src + "->" + i + ": " + dist[i]); } }面试陷阱点：
- 仅适用于非负权图（负权会导致贪心策略失效）
- 时间复杂度：普通实现O(V²)，优先队列优化后O(E + VlogV)
- 如何记录完整路径？→ 维护predecessor数组
4. Floyd算法：多源最短路径
Floyd算法通过动态规划解决任意两点间最短路径问题，代码简洁但思想深刻。
标准实现：
void floyd(int[][] graph) { int V = graph.length; int[][] dist = new int[V][V]; // 初始化距离矩阵 for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { dist[i][j] = graph[i][j]; } } // 动态规划核心 for (int k = 0; k < V; k++) { for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; } } } } // 输出结果 for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { System.out.print(dist[i][j] + " "); } System.out.println(); } }面试考察重点：
- 理解三重循环中k为什么必须放在最外层
- 空间复杂度O(V²)，时间复杂度O(V³)
- 如何处理负权边？→ 可以处理但不允许负权环
5. Prim与Kruskal算法：最小生成树
5.1 Prim算法的贪心实现
Prim算法从一个顶点开始，逐步扩展生成树。
优先队列优化版：
int primMST(int[][] graph) { int V = graph.length; boolean[] inMST = new boolean[V]; int[] key = new int[V]; Arrays.fill(key, Integer.MAX_VALUE); key[0] = 0; PriorityQueue<int[]> pq = new PriorityQueue<>( (a, b) -> a[1] - b[1]); pq.offer(new int[]{0, 0}); int totalWeight = 0; while (!pq.isEmpty()) { int[] curr = pq.poll(); int u = curr[0]; if (inMST[u]) continue; inMST[u] = true; totalWeight += curr[1]; for (int v = 0; v < V; v++) { if (graph[u][v] != 0 && !inMST[v] && graph[u][v] < key[v]) { key[v] = graph[u][v]; pq.offer(new int[]{v, key[v]}); } } } return totalWeight; }5.2 Kruskal算法的并查集实现
Kruskal算法按边权排序后逐步选择不形成环的边。
class Edge implements Comparable<Edge> { int src, dest, weight; public int compareTo(Edge other) { return this.weight - other.weight; } } int kruskalMST(List<Edge> edges, int V) { Collections.sort(edges); int[] parent = new int[V]; Arrays.fill(parent, -1); int mstWeight = 0; int edgeCount = 0; for (Edge edge : edges) { int x = find(parent, edge.src); int y = find(parent, edge.dest); if (x != y) { mstWeight += edge.weight; union(parent, x, y); if (++edgeCount == V-1) break; } } return mstWeight; }面试对比问题：
- Prim适合稠密图，Kruskal适合稀疏图
- 两者都是贪心算法，但策略不同
- 并查集的路径压缩优化能提升Kruskal效率
6. 面试实战技巧与高频考点
在技术面试中，图算法问题往往不是考察你会不会写算法，而是考察：
问题转化能力：
- 实际业务问题如何抽象为图模型
- 例如：社交网络中的好友推荐→图遍历问题
代码实现细节：
- 边界条件处理（空图、孤立顶点等）
- 避免常见错误（如BFS忘记标记已访问）
复杂度分析：
- 能准确分析时间/空间复杂度
- 根据问题特点选择合适算法
变种问题应对：
// 例如：带障碍物的网格最短路径（BFS变种） int shortestPath(int[][] grid) { // 方向数组：上、右、下、左 int[][] dirs = {{-1,0}, {0,1}, {1,0}, {0,-1}}; // 其余实现类似标准BFS }白板编码技巧：
- 先明确输入输出格式
- 写出关键步骤伪代码
- 最后填充具体实现
记住：面试官最想看到的不是你背熟了算法模板，而是你解决陌生问题的思维过程。当遇到图算法问题时，建议按照以下步骤应对：
- 澄清问题要求和约束条件
- 选择合适的数据结构表示图
- 根据问题特征选择算法范式
- 讨论可能的优化方案
- 编写清晰可读的代码
- 设计测试用例验证边界情况
