拓扑排序如何让任务有条不紊地执行：从Kahn算法到DFS的完整LeetCode通关指南

在大型软件项目的构建过程中，模块之间存在复杂的依赖关系：A模块依赖B模块，B模块又依赖C模块。构建系统必须找到一个合法的编译顺序，确保每个模块在其依赖项编译完成后才开始编译。这个问题的数学本质就是拓扑排序——给定一个有向无环图(DAG)，找到一个线性序列，使得对于每条有向边$u \to v$，顶点$u$都出现在顶点$v$之前。

拓扑排序的本质：为什么只有DAG才能拓扑排序

拓扑排序的核心前提是图必须是有向无环图(DAG)。为什么有环的图无法进行拓扑排序？考虑一个简单的环：$A \to B \to C \to A$。按照拓扑排序的定义，A应该在B之前，B应该在C之前，C应该在A之前——这显然是矛盾的。因此，环的存在意味着依赖关系存在死循环，无法找到合法的执行顺序。

对于无向图，每条边$u - v$都可以看作是$u \to v$和$v \to u$两条有向边，同样无法确定谁先谁后。这就是为什么拓扑排序只适用于DAG。

一个DAG可能存在多个合法的拓扑序列。例如，对于图$A \to B, A \to C$，$[A, B, C]$和$[A, C, B]$都是有效的拓扑序列。在实际应用中，我们只需要找到任意一个合法序列即可，或者在某些场景下需要找到字典序最小的序列。

拓扑排序示例图

图片来源: Interview Cake

两种经典实现：Kahn算法与DFS

Kahn算法：基于入度的BFS方法

Kahn算法的核心思想非常直观：入度为0的顶点没有任何前驱，可以安全地放在序列的最前面。算法步骤如下：

计算所有顶点的入度
将所有入度为0的顶点加入队列
从队列中取出一个顶点，加入结果序列
将该顶点的所有邻居的入度减1
如果某个邻居的入度变为0，加入队列
重复步骤3-5直到队列为空
如果结果序列的长度等于顶点数，说明拓扑排序成功；否则图中存在环

public class TopologicalSortKahn {
    public int[] topologicalSort(int numVertices, int[][] edges) {
        // 构建邻接表和入度数组
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[numVertices];
        
        for (int i = 0; i < numVertices; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            inDegree[edge[1]]++;
        }
        
        // 将入度为0的顶点加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numVertices; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        // BFS处理
        int[] result = new int[numVertices];
        int index = 0;
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result[index++] = node;
            
            for (int neighbor : graph.get(node)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        // 检查是否存在环
        if (index != numVertices) {
            return new int[0]; // 存在环，返回空数组
        }
        
        return result;
    }
}

Kahn算法的时间复杂度为$O(V + E)$，其中$V$是顶点数，$E$是边数。每个顶点和每条边都只被处理一次。空间复杂度为$O(V + E)$，用于存储邻接表和队列。

DFS方法：后序遍历的逆序

DFS方法的核心思想是：一个顶点只有在所有后继顶点都访问完成后，才能确定其在拓扑序列中的位置。具体步骤如下：

对图进行DFS遍历
当一个顶点的所有邻居都访问完成后，将该顶点压入栈中
最后将栈中的元素依次弹出，得到拓扑序列
使用状态数组检测环：正在访问的节点标记为"访问中"，访问完成的节点标记为"已访问"

public class TopologicalSortDFS {
    private static final int WHITE = 0; // 未访问
    private static final int GRAY = 1;  // 访问中
    private static final int BLACK = 2; // 已访问
    
    public int[] topologicalSort(int numVertices, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numVertices; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
        }
        
        int[] color = new int[numVertices];
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i < numVertices; i++) {
            if (color[i] == WHITE) {
                if (hasCycle(graph, i, color, stack)) {
                    return new int[0]; // 存在环
                }
            }
        }
        
        int[] result = new int[numVertices];
        for (int i = 0; i < numVertices; i++) {
            result[i] = stack.pop();
        }
        
        return result;
    }
    
    private boolean hasCycle(List<List<Integer>> graph, int node, 
                             int[] color, Deque<Integer> stack) {
        color[node] = GRAY;
        
        for (int neighbor : graph.get(node)) {
            if (color[neighbor] == GRAY) {
                return true; // 检测到环
            }
            if (color[neighbor] == WHITE && hasCycle(graph, neighbor, color, stack)) {
                return true;
            }
        }
        
        color[node] = BLACK;
        stack.push(node);
        return false;
    }
}

DFS方法同样具有$O(V + E)$的时间复杂度和$O(V + E)$的空间复杂度。

两种方法的选择

特性	Kahn算法	DFS方法
实现方式	BFS + 队列	DFS + 栈
环检测	自然支持	需要额外状态标记
字典序最小	使用优先队列即可	需要额外处理
空间开销	主要在队列	主要在递归栈

在实际应用中，如果需要字典序最小的拓扑序列，只需将Kahn算法中的普通队列替换为优先队列。这在处理课程安排、任务调度等需要确定性结果的场景中非常有用。

Kahn算法步骤图解

图片来源: Interview Cake

LeetCode经典题目解析

LeetCode 207. Course Schedule

判断是否可以完成所有课程的学习，本质上是检测图中是否存在环。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 构建邻接表和入度数组
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] pre : prerequisites) {
            graph.get(pre[1]).add(pre[0]);
            inDegree[pre[0]]++;
        }
        
        // Kahn算法
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int completed = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            completed++;
            
            for (int next : graph.get(course)) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        
        return completed == numCourses;
    }
}

复杂度分析：时间复杂度$O(V + E)$，空间复杂度$O(V + E)$。

LeetCode 210. Course Schedule II

在207题基础上，需要返回一个合法的课程学习顺序。

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] pre : prerequisites) {
            graph.get(pre[1]).add(pre[0]);
            inDegree[pre[0]]++;
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int[] result = new int[numCourses];
        int index = 0;
        
        while (!queue.isEmpty()) {
            int course = queue.poll();
            result[index++] = course;
            
            for (int next : graph.get(course)) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        
        return index == numCourses ? result : new int[0];
    }
}

LeetCode 269. Alien Dictionary

这是一道经典的"隐藏拓扑排序"题目。给定一组按外星语言字典序排列的单词，需要推断出该语言的字母顺序。

class Solution {
    public String alienOrder(String[] words) {
        // 构建图：每个字符需要先出现
        Map<Character, Set<Character>> graph = new HashMap<>();
        Map<Character, Integer> inDegree = new HashMap<>();
        
        // 初始化所有字符
        for (String word : words) {
            for (char c : word.toCharArray()) {
                graph.putIfAbsent(c, new HashSet<>());
                inDegree.putIfAbsent(c, 0);
            }
        }
        
        // 构建边：比较相邻单词
        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i];
            String w2 = words[i + 1];
            
            // 特殊情况：前一个单词更长且是后一个的前缀
            if (w1.length() > w2.length() && w1.startsWith(w2)) {
                return "";
            }
            
            int len = Math.min(w1.length(), w2.length());
            for (int j = 0; j < len; j++) {
                char c1 = w1.charAt(j);
                char c2 = w2.charAt(j);
                if (c1 != c2) {
                    if (!graph.get(c1).contains(c2)) {
                        graph.get(c1).add(c2);
                        inDegree.put(c2, inDegree.get(c2) + 1);
                    }
                    break; // 只需要第一个不同的字符
                }
            }
        }
        
        // Kahn算法
        Queue<Character> queue = new LinkedList<>();
        for (char c : inDegree.keySet()) {
            if (inDegree.get(c) == 0) {
                queue.offer(c);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            char c = queue.poll();
            sb.append(c);
            
            for (char next : graph.get(c)) {
                inDegree.put(next, inDegree.get(next) - 1);
                if (inDegree.get(next) == 0) {
                    queue.offer(next);
                }
            }
        }
        
        return sb.length() == graph.size() ? sb.toString() : "";
    }
}

关键点：通过比较相邻单词的第一个不同字符来构建字符之间的顺序关系，然后进行拓扑排序。

LeetCode 310. Minimum Height Trees

这道题是拓扑排序在无向图上的变体应用。要找到使树高度最小的根节点，需要从叶子节点开始逐层剥离。

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Arrays.asList(0);
        
        // 构建邻接表
        List<Set<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new HashSet<>());
        }
        
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        
        // 找到所有叶子节点（度数为1）
        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (graph.get(i).size() == 1) {
                leaves.add(i);
            }
        }
        
        // 逐层剥离
        int remaining = n;
        while (remaining > 2) {
            remaining -= leaves.size();
            List<Integer> newLeaves = new ArrayList<>();
            
            for (int leaf : leaves) {
                int neighbor = graph.get(leaf).iterator().next();
                graph.get(neighbor).remove(leaf);
                if (graph.get(neighbor).size() == 1) {
                    newLeaves.add(neighbor);
                }
            }
            
            leaves = newLeaves;
        }
        
        return leaves;
    }
}

核心思想：最小高度树的根一定是树的"中心"，即距离所有叶子节点最远的点。通过从外向内逐层剥离叶子节点，最终剩下的1-2个节点就是答案。

LeetCode 802. Find Eventual Safe States

找出所有"最终安全状态"的节点——即从该节点出发的所有路径都能到达终点的节点。这道题需要反向图 + 拓扑排序。

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        
        // 构建反向图和出度数组
        List<List<Integer>> reverseGraph = new ArrayList<>();
        int[] outDegree = new int[n];
        
        for (int i = 0; i < n; i++) {
            reverseGraph.add(new ArrayList<>());
        }
        
        for (int i = 0; i < n; i++) {
            outDegree[i] = graph[i].length;
            for (int j : graph[i]) {
                reverseGraph.get(j).add(i);
            }
        }
        
        // 从出度为0的节点开始（安全节点）
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (outDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        boolean[] safe = new boolean[n];
        while (!queue.isEmpty()) {
            int node = queue.poll();
            safe[node] = true;
            
            for (int prev : reverseGraph.get(node)) {
                outDegree[prev]--;
                if (outDegree[prev] == 0) {
                    queue.offer(prev);
                }
            }
        }
        
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (safe[i]) {
                result.add(i);
            }
        }
        
        return result;
    }
}

技巧：构建反向图后，出度为0的节点就是安全节点。通过拓扑排序可以找到所有能到达安全节点的节点。

LeetCode 1136. Parallel Courses

计算完成所有课程需要的最少学期数。这道题需要在拓扑排序过程中按层处理。

class Solution {
    public int minimumSemesters(int n, int[][] relations) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[n + 1];
        
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] rel : relations) {
            graph.get(rel[0]).add(rel[1]);
            inDegree[rel[1]]++;
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int semesters = 0;
        int completed = 0;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            semesters++;
            
            for (int i = 0; i < size; i++) {
                int course = queue.poll();
                completed++;
                
                for (int next : graph.get(course)) {
                    inDegree[next]--;
                    if (inDegree[next] == 0) {
                        queue.offer(next);
                    }
                }
            }
        }
        
        return completed == n ? semesters : -1;
    }
}

关键点：每一轮BFS处理完当前层的所有节点，就代表一个学期结束。

LeetCode 1857. Largest Color Value in a Directed Graph

这道题结合了拓扑排序 + 动态规划。需要在拓扑排序的过程中维护每个节点到当前节点的各颜色最大计数。

class Solution {
    public int largestPathValue(String colors, int[][] edges) {
        int n = colors.length();
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[n];
        
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            inDegree[edge[1]]++;
        }
        
        // dp[i][c] 表示到达节点i的路径中颜色c的最大出现次数
        int[][] dp = new int[n][26];
        Queue<Integer> queue = new LinkedList<>();
        
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
            dp[i][colors.charAt(i) - 'a'] = 1;
        }
        
        int processed = 0;
        int maxColor = 1;
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            processed++;
            
            for (int next : graph.get(node)) {
                // 更新next节点的颜色计数
                for (int c = 0; c < 26; c++) {
                    int count = dp[node][c] + (colors.charAt(next) - 'a' == c ? 1 : 0);
                    dp[next][c] = Math.max(dp[next][c], count);
                    maxColor = Math.max(maxColor, dp[next][c]);
                }
                
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        
        return processed == n ? maxColor : -1;
    }
}

核心思想：利用拓扑排序保证处理顺序的正确性，同时用DP维护各颜色的最大计数。

LeetCode 2115. Find All Possible Recipes from Given Supplies

给定食谱和原材料，找出可以制作的所有食谱。这是拓扑排序的典型应用——食谱之间的依赖关系。

class Solution {
    public List<String> findAllRecipes(String[] recipes, 
                                        List<List<String>> ingredients, 
                                        String[] supplies) {
        // 构建图
        Map<String, List<String>> graph = new HashMap<>();
        Map<String, Integer> inDegree = new HashMap<>();
        Set<String> available = new HashSet<>(Arrays.asList(supplies));
        
        for (String recipe : recipes) {
            inDegree.put(recipe, 0);
        }
        
        for (int i = 0; i < recipes.length; i++) {
            String recipe = recipes[i];
            for (String ing : ingredients.get(i)) {
                if (!available.contains(ing)) {
                    // 这个食材需要由其他食谱提供
                    graph.computeIfAbsent(ing, k -> new ArrayList<>()).add(recipe);
                    inDegree.put(recipe, inDegree.getOrDefault(recipe, 0) + 1);
                }
            }
        }
        
        // 拓扑排序
        Queue<String> queue = new LinkedList<>();
        for (String recipe : recipes) {
            if (inDegree.get(recipe) == 0) {
                queue.offer(recipe);
            }
        }
        
        List<String> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            String recipe = queue.poll();
            result.add(recipe);
            
            if (graph.containsKey(recipe)) {
                for (String dependent : graph.get(recipe)) {
                    inDegree.put(dependent, inDegree.get(dependent) - 1);
                    if (inDegree.get(dependent) == 0) {
                        queue.offer(dependent);
                    }
                }
            }
        }
        
        return result;
    }
}

LeetCode 2192. All Ancestors of a Node in a Directed Acyclic Graph

找出DAG中每个节点的所有祖先节点。

class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
        }
        
        List<List<Integer>> ancestors = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            ancestors.add(new ArrayList<>());
        }
        
        // 对每个节点执行BFS
        for (int i = 0; i < n; i++) {
            boolean[] visited = new boolean[n];
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(i);
            visited[i] = true;
            
            while (!queue.isEmpty()) {
                int node = queue.poll();
                for (int next : graph.get(node)) {
                    if (!visited[next]) {
                        visited[next] = true;
                        ancestors.get(next).add(i);
                        queue.offer(next);
                    }
                }
            }
        }
        
        // 排序结果
        for (List<Integer> list : ancestors) {
            Collections.sort(list);
        }
        
        return ancestors;
    }
}

LeetCode 2392. Build a Matrix With Conditions

根据行和列的约束条件构建矩阵。需要对行约束和列约束分别进行拓扑排序。

class Solution {
    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        int[] rowOrder = topologicalSort(k, rowConditions);
        int[] colOrder = topologicalSort(k, colConditions);
        
        if (rowOrder.length == 0 || colOrder.length == 0) {
            return new int[0][0];
        }
        
        // 记录每个数字在行和列中的位置
        int[] rowPos = new int[k + 1];
        int[] colPos = new int[k + 1];
        
        for (int i = 0; i < k; i++) {
            rowPos[rowOrder[i]] = i;
            colPos[colOrder[i]] = i;
        }
        
        int[][] matrix = new int[k][k];
        for (int num = 1; num <= k; num++) {
            matrix[rowPos[num]][colPos[num]] = num;
        }
        
        return matrix;
    }
    
    private int[] topologicalSort(int k, int[][] conditions) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[k + 1];
        
        for (int i = 0; i <= k; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] cond : conditions) {
            graph.get(cond[0]).add(cond[1]);
            inDegree[cond[1]]++;
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= k; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int[] result = new int[k];
        int index = 0;
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result[index++] = node;
            
            for (int next : graph.get(node)) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        
        return index == k ? result : new int[0];
    }
}

拓扑排序的实际应用

拓扑排序在工程实践中有着广泛的应用：

任务调度系统：在大数据处理平台中，多个任务之间存在依赖关系，调度系统需要找到一个合法的执行顺序。Apache Airflow等工具内部就使用了拓扑排序来确定DAG中任务的执行顺序。

编译系统：Make、Maven等构建工具需要根据文件依赖关系确定编译顺序。当某个文件修改后，系统需要重新编译所有依赖于它的文件。

课程安排系统：教育管理系统需要根据课程的先修要求生成合理的学习计划，确保学生按照正确的顺序修读课程。

电子设计自动化(EDA)：在集成电路设计中，逻辑门之间存在信号依赖关系，布局布线工具需要根据这些依赖确定处理顺序。

算法选择指南

面对一道图论题目，如何判断是否需要使用拓扑排序？以下是判断依据：

问题涉及依赖关系：题目中出现"必须先完成A才能做B"、“A依赖于B"等描述
需要确定执行顺序：问题要求找到一个合法的序列
检测环的存在：需要判断是否存在循环依赖
涉及DAG：题目明确提到有向无环图

当以上特征出现时，拓扑排序很可能就是解题的关键。在实际编码时，建议优先使用Kahn算法，因为它更容易理解和实现，同时也能自然地检测环的存在。当需要按层处理节点或需要字典序最小的结果时，Kahn算法配合优先队列是最优选择。

参考资料

Cormen, T. H., et al. Introduction to Algorithms, 3rd Edition, MIT Press, 2009.
Kahn, A. B. “Topological sorting of large networks.” Communications of the ACM, 5.11 (1962): 558-562.
GeeksforGeeks. “Topological Sorting.” https://www.geeksforgeeks.org/dsa/topological-sorting/
Interview Cake. “Topological Sort Algorithm.” https://www.interviewcake.com/concept/java/topological-sort
LeetCode Discussion. “How to identify and solve topological sort questions.” https://leetcode.com/discuss/interview-question/6136469/

拓扑排序的本质：为什么只有DAG才能拓扑排序#

两种经典实现：Kahn算法与DFS#

Kahn算法：基于入度的BFS方法#

DFS方法：后序遍历的逆序#

两种方法的选择#

LeetCode经典题目解析#

LeetCode 207. Course Schedule#

LeetCode 210. Course Schedule II#

LeetCode 269. Alien Dictionary#

LeetCode 310. Minimum Height Trees#

LeetCode 802. Find Eventual Safe States#

LeetCode 1136. Parallel Courses#

LeetCode 1857. Largest Color Value in a Directed Graph#

LeetCode 2115. Find All Possible Recipes from Given Supplies#

LeetCode 2192. All Ancestors of a Node in a Directed Acyclic Graph#

LeetCode 2392. Build a Matrix With Conditions#

拓扑排序的实际应用#

算法选择指南#

参考资料#

更多精彩内容

Tarjan算法为何能用一次DFS完成图论四大难题从强连通分量到桥与割点的完整LeetCode通关指南

最短路径算法为何如此重要从Dijkstra到Floyd的四种实现方式与LeetCode完整通关指南

深度优先与广度优先搜索:从栈与队列的选择到最短路径的博弈

回溯算法:从决策树到剪枝优化的完整LeetCode通关指南

股票买卖问题为何能用一套代码解决所有变体从状态机DP到贪心的统一框架