图算法：BFS、DFS、拓扑排序与最短路

这一课你将能做到

1. 用邻接表表示图，手写 BFS 和 DFS 遍历
2. 实现拓扑排序判断有向无环图（DAG）
3. 手写 Dijkstra 算法解决单源最短路

为什么要学

图是描述万物关系的「万能模型」。社交网络、地图导航、依赖管理、路由协议，底层都是图。不会图算法，面对关系型问题就只能拍脑袋。

人话：图就是点和线的集合。BFS 是「水波纹扩散」，DFS 是「一条道走到黑」，拓扑排序是「先修课排序」，Dijkstra 是「贪心走最近」。

先建立图像

有向图:    0 → 1 → 2
          ↓   ↓
          3 → 4

邻接表表示:
0: [1, 3]
1: [2, 4]
2: []
3: [4]
4: []

最短路 (Dijkstra):
      0
     /|\
   4/ 1 \5
   /  |  \
  1   2   3

0→2 的最短距离: 1
0→1 的最短距离: 4

跟着做

步骤 1：图的邻接表表示

import java.util.*;

public class Main {
    // 有向图
    static List<List<Integer>> buildGraph(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
        }
        return graph;
    }
    
    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0,1},{0,3},{1,2},{1,4},{3,4}};
        List<List<Integer>> g = buildGraph(n, edges);
        for (int i = 0; i < n; i++) {
            System.out.println(i + ": " + g.get(i));
        }
    }
}

步骤 2：图的 BFS 遍历

import java.util.*;

public class Main {
    public static List<Integer> bfs(List<List<Integer>> graph, int start) {
        List<Integer> res = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.size()];
        queue.offer(start);
        visited[start] = true;
        
        while (!queue.isEmpty()) {
            int u = queue.poll();
            res.add(u);
            for (int v : graph.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    queue.offer(v);
                }
            }
        }
        return res;
    }
    
    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0,1},{0,3},{1,2},{1,4},{3,4}};
        List<List<Integer>> g = buildGraph(n, edges);
        System.out.println(bfs(g, 0)); // [0, 1, 3, 2, 4]
    }
    
    static List<List<Integer>> buildGraph(int n, int[][] edges) {
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) g.get(e[0]).add(e[1]);
        return g;
    }
}

步骤 3：图的 DFS 遍历

import java.util.*;

public class Main {
    public static List<Integer> dfs(List<List<Integer>> graph, int start) {
        List<Integer> res = new ArrayList<>();
        boolean[] visited = new boolean[graph.size()];
        Stack<Integer> stack = new Stack<>();
        stack.push(start);
        
        while (!stack.isEmpty()) {
            int u = stack.pop();
            if (visited[u]) continue;
            visited[u] = true;
            res.add(u);
            // 注意：倒序入栈保证正序输出
            List<Integer> neighbors = graph.get(u);
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                int v = neighbors.get(i);
                if (!visited[v]) stack.push(v);
            }
        }
        return res;
    }
    
    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0,1},{0,3},{1,2},{1,4},{3,4}};
        List<List<Integer>> g = buildGraph(n, edges);
        System.out.println(dfs(g, 0)); // [0, 1, 2, 4, 3]
    }
    
    static List<List<Integer>> buildGraph(int n, int[][] edges) {
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) g.get(e[0]).add(e[1]);
        return g;
    }
}

步骤 4：拓扑排序（Kahn 算法）

import java.util.*;

public class Main {
    public static List<Integer> topoSort(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[n];
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] e : edges) {
            graph.get(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);
        }
        
        List<Integer> res = new ArrayList<>();
        while (!queue.isEmpty()) {
            int u = queue.poll();
            res.add(u);
            for (int v : graph.get(u)) {
                inDegree[v]--;
                if (inDegree[v] == 0) queue.offer(v);
            }
        }
        
        return res.size() == n ? res : Collections.emptyList(); // 有环时返回空
    }
    
    public static void main(String[] args) {
        int[][] edges = {{0,1},{1,2},{0,2},{2,3},{3,4}};
        System.out.println(topoSort(5, edges)); // [0, 1, 2, 3, 4]
        
        int[][] cycle = {{0,1},{1,2},{2,0}};
        System.out.println(topoSort(3, cycle)); // []
    }
}

步骤 5：Dijkstra 最短路

import java.util.*;

public class Main {
    static class Edge {
        int to, weight;
        Edge(int t, int w) { to = t; weight = w; }
    }
    
    static class Node {
        int dist, id;
        Node(int d, int i) { dist = d; id = i; }
    }
    
    public static int[] dijkstra(int n, List<List<Edge>> graph, int start) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.dist));
        pq.offer(new Node(0, start));
        
        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            if (cur.dist > dist[cur.id]) continue;
            for (Edge e : graph.get(cur.id)) {
                if (dist[cur.id] + e.weight < dist[e.to]) {
                    dist[e.to] = dist[cur.id] + e.weight;
                    pq.offer(new Node(dist[e.to], e.to));
                }
            }
        }
        return dist;
    }
    
    public static void main(String[] args) {
        int n = 5;
        List<List<Edge>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        g.get(0).add(new Edge(1, 4));
        g.get(0).add(new Edge(2, 1));
        g.get(1).add(new Edge(3, 1));
        g.get(2).add(new Edge(1, 2));
        g.get(2).add(new Edge(3, 5));
        g.get(3).add(new Edge(4, 3));
        
        int[] dist = dijkstra(n, g, 0);
        System.out.println(Arrays.toString(dist)); // [0, 3, 1, 4, 7]
    }
}

讲清楚要点

1. 图的存储：邻接表省空间 O(V+E)，适合稀疏图；邻接矩阵 O(V²)，适合稠密图。
2. 拓扑排序：Kahn 算法用入度数组，时间 O(V+E)。能检测环。
3. Dijkstra 限制：不能处理负权边。负权边用 Bellman-Ford 或 SPFA。
4. 判题场景：课程表=拓扑排序；地图导航=Dijkstra；社交网络=BFS/DFS。

你可能会懵的地方

• BFS 和 DFS 在图上有什么区别？ BFS 求最短路径（无权图），DFS 找连通分量或拓扑序。BFS 空间 O(V)，DFS 递归 O(V)。

• 拓扑排序为什么能检测环？ 有环时入度无法全部减到 0，输出节点数 < V。

• Dijkstra 为什么贪心是对的？ 每次选未确定最短路径中距离最小的点，一旦确定就不会被更新。非负权边保证这一点。

• 图的判题中 n 最大多少？ n≤10^3 可以邻接矩阵；n≤10^5 必须邻接表。稠密图（E≈V²）注意内存。

• 最小生成树和最短路的区别？ MST 连接所有点且总边权最小（Prim/Kruskal）；最短路是两点间距离最小（Dijkstra）。

错法对照

错法	问题	正解
无向图只加一条边	遍历不到反向	graph.get(u).add(v); graph.get(v).add(u);
Dijkstra 不判断 cur.dist > dist[cur.id]	过期节点重复入堆，效率差	poll 后检查，跳过过期节点
拓扑排序不判断输出数量	有环返回不完整结果	res.size() != n 说明有环
DFS 不标记已访问	无限循环	入栈/出栈时标记 visited
邻接表数组开 new ArrayList[n]	元素为 null	循环 add(new ArrayList<>())

卡点急救

1. 图遍历结果和预期不同：检查是无向图还是有向图，是否有重复边。
2. Dijkstra TLE：用堆优化（O(E log V)），不用数组扫描（O(V²)）。稀疏图用堆，稠密图用数组。
3. 拓扑排序返回空：检查是否输入了环的数据，或入度统计错误。

面试常问

• 拓扑排序的应用场景？ 课程选修、任务调度、编译依赖、数据库死锁检测。核心是「先处理入度为 0 的点」。

• Dijkstra 和 Floyd 的区别？ Dijkstra 是单源最短路 O(E log V)，适合单点出发；Floyd 是多源最短路 O(V³)，适合所有点对。负权边都用不了 Dijkstra。

• 怎么判断图是否有环？ 有向图用拓扑排序（Kahn）或 DFS 回边检测；无向图用并查集或 DFS 父节点检测。

自测三问

1. 拓扑排序的输出是否唯一？什么情况下唯一？
2. Dijkstra 为什么不能处理负权边？
3. 稠密图和稀疏图分别适合用什么存储方式？

小结一句话

图是描述关系的万能模型，BFS/DFS 遍历所有可能，拓扑排序解决依赖问题，Dijkstra 找到最短路径；掌握图算法，就掌握了关系型问题的解法。

延伸

• Java 官方文档：PriorityQueue
• 下一课：高级数据结构——Trie、并查集与跳表。