跳到主要内容

图论基础

问题​

Java 中图相关的常见算法题有哪些？

答案​

图的表示​

邻接表（最常用）
// 方式一：List 数组
List<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
graph[0].add(1);  // 0 → 1

// 方式二：Map（节点非连续时）
Map<Integer, List<Integer>> graph = new HashMap<>();

课程表（LeetCode 207）—— 拓扑排序 BFS​

BFS Kahn 算法
public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[] inDegree = new int[numCourses];
    List<Integer>[] graph = new ArrayList[numCourses];
    for (int i = 0; i < numCourses; i++) graph[i] = new ArrayList<>();
    
    // 建图 + 统计入度
    for (int[] pre : prerequisites) {
        graph[pre[1]].add(pre[0]);
        inDegree[pre[0]]++;
    }
    
    // 入度为 0 的节点入队
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) queue.offer(i);
    }
    
    int count = 0;
    while (!queue.isEmpty()) {
        int cur = queue.poll();
        count++;
        for (int next : graph[cur]) {
            if (--inDegree[next] == 0) queue.offer(next);
        }
    }
    return count == numCourses;  // 全部节点都被处理 = 无环
}

岛屿数量（LeetCode 200）—— DFS 洪水填充​

DFS 标记已访问
public int numIslands(char[][] grid) {
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                count++;
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length 
        || grid[i][j] != '1') return;
    grid[i][j] = '0';  // 标记已访问
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

克隆图（LeetCode 133）—— DFS + HashMap​

HashMap 记录已克隆节点
Map<Node, Node> visited = new HashMap<>();

public Node cloneGraph(Node node) {
    if (node == null) return null;
    if (visited.containsKey(node)) return visited.get(node);
    
    Node clone = new Node(node.val);
    visited.put(node, clone);
    for (Node neighbor : node.neighbors) {
        clone.neighbors.add(cloneGraph(neighbor));
    }
    return clone;
}

最短路径 —— BFS（无权图）​

网格最短路径 BFS
public int shortestPath(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();
    boolean[][] visited = new boolean[m][n];
    queue.offer(new int[]{0, 0});
    visited[0][0] = true;
    int steps = 0;
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int[] cur = queue.poll();
            if (cur[0] == m - 1 && cur[1] == n - 1) return steps;
            for (int[] d : dirs) {
                int nx = cur[0] + d[0], ny = cur[1] + d[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n 
                    && !visited[nx][ny] && grid[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    queue.offer(new int[]{nx, ny});
                }
            }
        }
        steps++;
    }
    return -1;
}

常见面试问题​

Q1: BFS 和 DFS 分别适合什么题？​

答案：

算法适用场景
BFS最短路径（无权图）、层序遍历、拓扑排序
DFS连通分量、路径搜索、回溯、判环

Q2: 如何判断有向图中是否有环？​

答案：

  • BFS 拓扑排序：处理完的节点数 < 总节点数 → 有环
  • DFS 三色标记：白色（未访问）、灰色（访问中）、黑色（已完成），遇到灰色节点 → 有环

Q3: Dijkstra 算法什么时候用？​

答案：

求带权图的单源最短路径（边权非负）。用优先队列优化后时间 O(Elog⁡V)O(E \log V)。Java 面试更常考 BFS 无权最短路径和拓扑排序。

相关链接​