BFS 实现拓扑排序：原理与 LeetCode 实战

一、拓扑排序基础

1.1 有向无环图（DAG）

有向无环图是指一个没有回路的有向图。简单来说，如果从某个顶点出发无法经过若干条边回到该点，那么这个图就是 DAG。

1.2 AOV 网：顶点活动图

在 DAG 的基础上，我们用顶点表示活动，用边表示活动执行的先后顺序关系。

1.3 什么是拓扑排序

拓扑排序的核心目标是找到做事的先后顺序。具体做法是：每次找出入度为 0 的点，将其加入结果序列，并删除该点相连的边，重复此过程直到所有点都被处理或发现无法继续。

1.4 BFS 实现思路

借助队列来实现 BFS 遍历，流程如下：

1. 初始化：将所有入度为 0 的点加入队列。
2. 循环处理：当队列不为空时，取出队头元素加入最终结果。
3. 更新依赖：删除与该点相连的边，即减少相邻点的入度。
4. 入队判断：若某相邻点入度变为 0，则将其加入队列。

二、经典案例解析

2.1 课程表 I（检测可行性）

题目核心：给定课程数量和先修条件，判断是否能完成所有课程。

解题逻辑： 我们使用邻接表 List<List<Integer>> 来表示图，下标对应课程 ID，数组内容指向后续课程。遍历先修条件数组构建图的同时统计每个课程的入度。

这里有个细节要注意：如果没有任何先修条件，直接返回 true；另外，每个点只能入队一次，避免重复计算。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int m = prerequisites.length;
        if (m == 0) return true;
        
        // 建图：邻接表
        List<List<Integer>> edges = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        
        Queue<Integer> queue = new LinkedList<>();
        int[] inDegree = new int[numCourses];
        boolean[] visited = new boolean[numCourses];
        
        // 统计入度并建图
        for (int i = 0; i < m; i++) {
            int course = prerequisites[i][0];
            int pre = prerequisites[i][1];
            edges.get(pre).add(course);
            inDegree[course]++;
        }
        
        // 入度为 0 的点入队
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
                visited[i] = true;
            }
        }
        
        if (queue.isEmpty()) return false;
        
        // BFS 遍历
        while (!queue.isEmpty()) {
            int tmp = queue.poll();
            // 销毁边：减少邻居入度
            for (int neighbor : edges.get(tmp)) {
                inDegree[neighbor]--;
                // 入度为 0 且未访问过才入队
                if (inDegree[neighbor] == 0 && !visited[neighbor]) {
                    queue.add(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
        
        // 检查是否所有课程都能被访问
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] != 0) return false;
        }
        return true;
    }
}

2.2 课程表 II（获取顺序）

题目核心：不仅要判断能否完成，还要返回具体的学习顺序。

解题逻辑： 基本思路与上一题一致，区别在于我们需要记录出队的顺序。我们可以用一个数组来存储结果，每弹出一个节点就填入数组。

注意边界情况：如果先修条件为空，直接返回 0 到 numCourses-1 的顺序即可。最后比较计数器与总课程数，不一致说明存在环，返回空数组。

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] result = new int[numCourses];
        int count = 0;
        
        int m = prerequisites.length;
        if (m == 0) {
            for (int i = 0; i < numCourses; i++) result[i] = i;
            return result;
        }
        
        List<List<Integer>> edges = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[numCourses];
        int[] inDegree = new int[numCourses];
        
        // 建图与统计入度
        for (int i = 0; i < m; i++) {
            int course = prerequisites[i][0];
            int pre = prerequisites[i][1];
            edges.get(pre).add(course);
            inDegree[course]++;
        }
        
        // 初始入队
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
                visited[i] = true;
            }
        }
        
        // BFS 过程
        while (!queue.isEmpty()) {
            int tmp = queue.poll();
            result[count++] = tmp;
            
            for (int neighbor : edges.get(tmp)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0 && !visited[neighbor]) {
                    queue.add(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
        
        // 验证结果
        return (count != numCourses) ? new int[0] : result;
    }
}

2.3 火星词典（字符串转图）

题目核心：根据字典序推导字符顺序。

解题逻辑： 这道题稍微复杂一点，因为需要先通过字符串对比构建图。两个字符串第一个不同位置的字符决定了它们的大小关系，例如 "wrt" 和 "wrf" 意味着 t -> f。

需要特别处理一种非法情况：前缀冲突。比如 "abc" 排在 "ab" 前面，这是不合法的，因为短字符串不能比长字符串大。

class Solution {
    Map<Character, Set<Character>> edges = new HashMap<>();
    Map<Character, Integer> inDegree = new HashMap<>();
    boolean illegal = false;
    
    public String alienOrder(String[] words) {
        // 初始化所有字符入度为 0
        for (String s : words) {
            for (char ch : s.toCharArray()) {
                inDegree.put(ch, 0);
            }
        }
        
        // 建图
        for (int i = 0; i < words.length - 1; i++) {
            addEdge(words[i], words[i + 1]);
            if (illegal) return "";
        }
        
        // 拓扑排序初始化
        Queue<Character> queue = new LinkedList<>();
        for (char ch : inDegree.keySet()) {
            if (inDegree.get(ch) == 0) queue.add(ch);
        }
        
        // BFS 构建结果
        StringBuilder ret = new StringBuilder();
        while (!queue.isEmpty()) {
            char tmp = queue.poll();
            ret.append(tmp);
            
            if (edges.containsKey(tmp)) {
                for (char ch : edges.get(tmp)) {
                    inDegree.put(ch, inDegree.get(ch) - 1);
                    if (inDegree.get(ch) == 0) queue.add(ch);
                }
            }
        }
        
        // 检查是否有环
        return ret.length() != inDegree.size() ? "" : ret.toString();
    }
    
    private void addEdge(String a, String b) {
        int n = Math.min(a.length(), b.length());
        int i = 0;
        for (; i < n; i++) {
            char c1 = a.charAt(i);
            char c2 = b.charAt(i);
            if (c1 != c2) {
                edges.putIfAbsent(c1, new HashSet<>());
                if (!edges.get(c1).contains(c2)) {
                    edges.get(c1).add(c2);
                    inDegree.put(c2, inDegree.get(c2) + 1);
                }
                break;
            }
        }
        // 处理前缀非法情况：如 abc 在 ab 前面
        if (i == b.length() && a.length() > b.length()) {
            illegal = true;
        }
    }
}