面试官最爱问的图算法：从DFS/BFS到Dijkstra，用Java代码实战带你一次搞懂

面试官最爱问的图算法从DFS/BFS到Dijkstra用Java代码实战带你一次搞懂在技术面试中图算法是考察候选人基本功和逻辑思维能力的经典题型。无论是大厂校招还是社招从简单的DFS/BFS遍历到复杂的最短路径问题都是面试官检验候选人算法素养的试金石。本文将用Java代码实战带你系统掌握面试中最常出现的五大图算法并揭示面试官在这些题目背后真正想考察的解题思维。1. 图的基础表示与核心概念在深入算法之前我们需要建立对图数据结构的正确理解。图由顶点(Vertex)和边(Edge)组成常见表示方式有邻接矩阵和邻接表两种。邻接矩阵实现Java版public class Graph { private ListInteger 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(VE)明确图的类型有向/无向和边权特性加权/未加权2. 深度优先搜索(DFS)与广度优先搜索(BFS)2.1 DFS的递归与非递归实现DFS如同走迷宫时选择一条路走到底再回溯探索其他路径。面试中常要求比较递归与迭代实现的差异。递归版DFSvoid 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); } } }栈实现的迭代版DFSvoid dfsStack(int start, int[][] graph) { StackInteger 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像水波纹一样层层扩散适合求解最短路径问题无权图。队列实现BFSvoid bfs(int start, int[][] graph) { QueueInteger 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(VE)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; PriorityQueueint[] 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; PriorityQueueint[] 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 ComparableEdge { int src, dest, weight; public int compareTo(Edge other) { return this.weight - other.weight; } } int kruskalMST(ListEdge 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 }白板编码技巧先明确输入输出格式写出关键步骤伪代码最后填充具体实现记住面试官最想看到的不是你背熟了算法模板而是你解决陌生问题的思维过程。当遇到图算法问题时建议按照以下步骤应对澄清问题要求和约束条件选择合适的数据结构表示图根据问题特征选择算法范式讨论可能的优化方案编写清晰可读的代码设计测试用例验证边界情况