图论：BFS / DFS / 最短路径

图是面试中难度最高的数据结构之一，考查频率极高。本文系统梳理图的表示方式、遍历策略、拓扑排序、并查集和 Dijkstra 最短路算法。

---

1. 图的表示方式

邻接矩阵

用二维数组 matrix[i][j] 表示顶点 i 到顶点 j 的边权重（0 表示无边）。

• 优点：O(1) 查询任意两点是否相连
• 缺点：空间 O(V²)，稀疏图浪费严重

邻接表

每个顶点维护一个链表，存储所有邻居节点。

• 优点：空间 O(V+E)，适合稀疏图（面试中最常用）
• 缺点：查询两点是否相连需 O(degree)

Java 邻接表建图

// 方式1：List数组（最常用）
List<int[]>[] graph = new List[n]; // int[]{neighbor, weight}
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
graph[u].add(new int[]{v, w}); // 添加边 u->v，权重w

// 方式2：Map<Integer, List<Integer>>（顶点非连续编号时）
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);

---

2. DFS 深度优先遍历

思路：从起点出发，沿一条路径走到底，再回溯探索其他路径。用递归或显式栈实现。

Java 实现

boolean[] visited;

public void dfs(List<Integer>[] graph, int node) {
    visited[node] = true;
    System.out.print(node + " ");
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor);
        }
    }
}

// 迭代版本（避免递归栈溢出）
public void dfsIterative(List<Integer>[] graph, int start) {
    boolean[] visited = new boolean[graph.length];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (visited[node]) continue;
        visited[node] = true;
        System.out.print(node + " ");
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) stack.push(neighbor);
        }
    }
}

---

3. BFS 广度优先遍历

思路：从起点出发，逐层扩散，先访问距离为1的节点，再访问距离为2的节点。用队列实现，天然求最短路（无权图）。

Java 实现

public int bfs(List<Integer>[] graph, int start, int target) {
    boolean[] visited = new boolean[graph.length];
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;
    int steps = 0;
    while (!queue.isEmpty()) {
        int size = queue.size(); // 逐层处理
        for (int i = 0; i < size; i++) {
            int node = queue.poll();
            if (node == target) return steps;
            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
        steps++;
    }
    return -1; // 不可达
}

---

4. 拓扑排序（Kahn 算法）

适用场景：有向无环图（DAG），输出顶点的线性顺序使得每条边 u→v 中 u 在 v 之前。

核心：反复找入度为 0 的节点，加入结果，并将其邻居的入度减 1。

初始状态

各节点入度：0→0, 1→0, 2→2, 3→1, 4→2

队列（入度为0）：[0, 1]

移除节点0

0 ✓

1

2 (入度1→1)

3

4

结果：[0]，节点2入度：2→1

移除节点1

0 ✓

1 ✓

2 (入度0→队列)

3 (入度0→队列)

4

结果：[0, 1]，2 和 3 入度变为 0，进入队列

最终结果

依次移除 2→3→4：

0

1

2

3

4

拓扑序：[0, 1, 2, 3, 4]（不唯一，取决于队列顺序）

Java 实现

public int[] topologicalSort(int n, int[][] edges) {
    List<Integer>[] graph = new List[n];
    int[] inDegree = new int[n];
    for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
    for (int[] e : edges) {
        graph[e[0]].add(e[1]);
        inDegree[e[1]]++;
    }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) queue.offer(i);
    }
    int[] result = new int[n];
    int idx = 0;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        result[idx++] = node;
        for (int next : graph[node]) {
            if (--inDegree[next] == 0) queue.offer(next);
        }
    }
    return idx == n ? result : new int[0]; // idx < n 说明有环
}

---

5. 并查集（Union-Find）

适用场景：动态连通性问题——判断两点是否在同一连通分量，合并两个分量。

两大优化：

• 路径压缩：find 时将沿途节点直接连到根，压缩树高
• 按秩合并：union 时将矮树挂到高树下

class UnionFind {
    int[] parent, rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = 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 px = find(x), py = find(y);
        if (px == py) return false; // 已连通，加入此边会成环
        if (rank[px] < rank[py]) { int t = px; px = py; py = t; }
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        return true;
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

---

6. Dijkstra 最短路径

适用：有向/无向带非负权图，求单源最短路径。

初始状态

距离表：{S:0, A:∞, B:∞, C:∞, D:∞, E:∞}

优先队列（最小堆）：[(0, S)]

处理 S（距离0）

当前：S，距离 = 0
更新邻居：A → min(∞, 0+4) = 4，B → min(∞, 0+2) = 2

距离表：{S:0, A:4, B:2, C:∞, D:∞, E:∞}

队列：[(2,B), (4,A)]

处理 B（距离2）

当前：B，距离 = 2
更新邻居：A → min(4, 2+3) = 4（不更新），D → min(∞, 2+5) = 7

距离表：{S:0, A:4, B:2, C:∞, D:7, E:∞}

处理 A（距离4）

当前：A，距离 = 4
更新邻居：C → min(∞, 4+3) = 7，D → min(7, 4+1) = 5（更新！）

距离表：{S:0, A:4, B:2, C:7, D:5, E:∞}

最终结果

继续处理 D(5)→E(7)，C(7)→E已更新：

S: 0

B: 2

A: 4

D: 5

C: 7

E: 7

S 到 E 的最短距离为 7，路径：S→B→A→D→E（2+1+1+2=... 不对，实为 S→A→D→E = 4+1+2=7）

Java 实现

public int[] dijkstra(int[][] graph, int src) {
    int n = graph.length;
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    // 优先队列：[距离, 节点]
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[]{0, src});
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], u = curr[1];
        if (d > dist[u]) continue; // 已找到更短路径，跳过
        for (int v = 0; v < n; v++) {
            if (graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    return dist;
}

---

精选题解

LC 200 岛屿数量（DFS）

题目：给定二维网格，'1' 为陆地，'0' 为水，计算岛屿数量（四方向相连的陆地算一个岛）。

思路：遍历每个格子，遇到 '1' 就 DFS 将整个岛屿染成 '0'（避免重复计数），计数器 +1。

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);
}

时间：O(M×N)，空间：O(M×N)（递归栈）

---

LC 207 课程表（拓扑排序检测环）

题目：n 门课，prerequisites[i] = [a,b] 表示学 a 前必须学 b，判断能否完成所有课程。

思路：建有向图，做拓扑排序。如果所有节点都能被处理（无环），返回 true。

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<Integer>[] graph = new List[numCourses];
    int[] inDegree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) graph[i] = new ArrayList<>();
    for (int[] p : prerequisites) {
        graph[p[1]].add(p[0]);
        inDegree[p[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 course = queue.poll();
        count++;
        for (int next : graph[course]) {
            if (--inDegree[next] == 0) queue.offer(next);
        }
    }
    return count == numCourses;
}

时间：O(V+E)，空间：O(V+E)

---

LC 127 单词接龙（BFS 最短路）

题目：给定词典，每次只改一个字母，从 beginWord 变成 endWord，求最短变换步数。

思路：BFS 逐层扩展，每层枚举当前单词所有可能的一字之差邻居（26个字母替换每个位置），找到目标即返回层数。

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> wordSet = new HashSet<>(wordList);
    if (!wordSet.contains(endWord)) return 0;
    Queue<String> queue = new LinkedList<>();
    queue.offer(beginWord);
    wordSet.remove(beginWord);
    int steps = 1;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String word = queue.poll();
            char[] chars = word.toCharArray();
            for (int j = 0; j < chars.length; j++) {
                char original = chars[j];
                for (char c = 'a'; c <= 'z'; c++) {
                    chars[j] = c;
                    String next = new String(chars);
                    if (next.equals(endWord)) return steps + 1;
                    if (wordSet.contains(next)) {
                        wordSet.remove(next);
                        queue.offer(next);
                    }
                }
                chars[j] = original;
            }
        }
        steps++;
    }
    return 0;
}

时间：O(M²×N)，M为单词长度，N为词典大小

---

LC 684 冗余连接（并查集）

题目：树中加入一条多余的边使得图有环，找到这条边（如果有多条答案，返回最后出现的）。

思路：依次添加每条边，用并查集判断这条边的两端是否已连通。若已连通，这条边就是冗余边。

public int[] findRedundantConnection(int[][] edges) {
    int n = edges.length;
    UnionFind uf = new UnionFind(n + 1);
    for (int[] edge : edges) {
        if (!uf.union(edge[0], edge[1])) {
            return edge; // 加入这条边时两端已连通，即为冗余边
        }
    }
    return new int[0];
}

时间：O(N × α(N))（α 为反阿克曼函数，近似 O(1)）

---

知识点速查

算法	数据结构	时间复杂度	典型题目
DFS	递归栈 / 显式栈	O(V+E)	岛屿数量、路径搜索
BFS	队列	O(V+E)	最短路（无权）、单词接龙
拓扑排序	队列 + 入度数组	O(V+E)	课程表、任务调度
并查集	数组	O(α(N))	连通分量、检测环
Dijkstra	优先队列	O((V+E)logV)	有权图最短路
Bellman-Ford	数组	O(VE)	含负权边最短路