图算法：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;
    }
}