图论基础：图的表示、拓扑排序与经典例题

说实话，图论这块内容，我当年学的时候也觉得挺抽象的。一堆节点和边，画在纸上还行，一写代码就懵。但后来做项目多了才发现，图这玩意儿无处不在——社交网络的好友关系、地图导航的路径规划、甚至你点外卖时的配送路线优化，背后都是图在干活。

今天咱们就聊聊图论里最基础、也最实用的几个点。我会结合自己踩过的坑，帮你把这块啃下来。

图的表示方式：邻接矩阵 vs 邻接表

图怎么存？这是写任何图算法前必须想清楚的事。我个人习惯用两种方式，各有各的适用场景。

表示方式	空间复杂度	判断边是否存在	遍历邻居	适用场景
邻接矩阵	O(V²)	O(1)	O(V)	稠密图、小规模图
邻接表	O(V+E)	O(degree)	O(degree)	稀疏图、大规模图

邻接矩阵说白了就是一个二维数组，graph[i][j] = 1 表示 i 到 j 有边。优点是判断两点是否相连特别快，缺点是太费内存。你想想看，10000 个节点，光矩阵就得 1 亿个格子，这谁顶得住？

邻接表就聪明多了——每个节点只存它自己的邻居。用 List<Integer>[] 或者 Map<Integer, List<Integer>> 都行。我在项目中几乎只用邻接表，因为实际场景的图基本都是稀疏的。

拓扑排序：有向无环图的线性化

拓扑排序，说白了就是给有向无环图（DAG）排个序，保证每条边的起点都在终点前面。这玩意儿在任务调度、课程安排、编译依赖里特别常见。

实现方式有两种：Kahn 算法（BFS 思路）和 DFS 后序遍历。我个人更推荐 Kahn 算法，因为它直观，而且能顺便检测环。

// Kahn 算法模板
public int[] topologicalSort(int n, int[][] edges) {
    // 1. 建图 + 统计入度
    List<Integer>[] graph = new ArrayList[n];
    int[] indegree = new int[n];
    for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
    for (int[] edge : edges) {
        int from = edge[0], to = edge[1];
        graph[from].add(to);
        indegree[to]++;
    }
    
    // 2. 入度为 0 的节点入队
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }
    
    // 3. BFS 拓扑排序
    int[] result = new int[n];
    int idx = 0;
    while (!queue.isEmpty()) {
        int cur = queue.poll();
        result[idx++] = cur;
        for (int next : graph[cur]) {
            indegree[next]--;
            if (indegree[next] == 0) queue.offer(next);
        }
    }
    
    // 4. 检查是否有环
    return idx == n ? result : new int[0];
}

经典例题一：课程表 II

这道题是 LeetCode 第 210 题，也是拓扑排序的经典应用。题目说你要修 n 门课，有些课有前置课程，让你返回一个合理的修课顺序。

嗯，这里要注意：题目可能给的是有环的图——比如 A 依赖 B，B 又依赖 A，那就没法排了。所以拓扑排序的结果长度如果小于 n，说明有环，直接返回空数组。

我当初刷这道题时犯过一个错：把入度数组初始化为 0，但忘了处理节点编号从 0 开始还是从 1 开始。后来养成了习惯，先看题目说明，再动手写代码。

// 课程表 II 的完整解法
public int[] findOrder(int numCourses, int[][] prerequisites) {
    // 建图
    List<Integer>[] graph = new ArrayList[numCourses];
    int[] indegree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) graph[i] = new ArrayList<>();
    for (int[] pre : prerequisites) {
        int from = pre[1], to = pre[0];
        graph[from].add(to);
        indegree[to]++;
    }
    
    // 入度为 0 的节点入队
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }
    
    // BFS
    int[] result = new int[numCourses];
    int idx = 0;
    while (!queue.isEmpty()) {
        int cur = queue.poll();
        result[idx++] = cur;
        for (int next : graph[cur]) {
            indegree[next]--;
            if (indegree[next] == 0) queue.offer(next);
        }
    }
    
    return idx == numCourses ? result : new int[0];
}

经典例题二：克隆图

LeetCode 第 133 题，克隆图。这题看着简单，其实暗藏玄机。图里可能有环，所以不能简单递归复制，否则会死循环。

解法是用一个 HashMap 做缓存，记录已经克隆过的节点。每次遇到一个新节点，先创建它的副本，存到 map 里，然后再递归处理它的邻居。

// 克隆图的 DFS 解法
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, new ArrayList<>());
    visited.put(node, clone);
    
    // 递归克隆邻居
    for (Node neighbor : node.neighbors) {
        clone.neighbors.add(cloneGraph(neighbor));
    }
    
    return clone;
}

知识体系总览

下面这张图是我自己整理的图论基础知识结构，帮你快速建立整体认知。

图论这块，说白了就是「节点 + 边」的学问。你只要把图的表示搞明白，拓扑排序的模板背熟，课程表 II 和克隆图这两道题吃透，面试里遇到图论题基本就不慌了。

我记得自己第一次在面试里写拓扑排序时，手都在抖。后来练了十几道题，闭着眼都能写出来。你也别急，多练几遍，肌肉记忆就形成了。

---

公众号:蓝海资料掘金营，微信deep3321