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

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;
        }
    }
}