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

三、LeetCode 210. 课程表 II

这道题不仅要求判断能否完成，还需要返回具体的学习顺序。如果无法完成，返回空数组。

解题思路

基本流程与上一题一致，区别在于需要记录出队的顺序。我们可以预先初始化结果数组，每弹出一个节点就填入结果中。最后比较已处理节点数与总课程数是否一致。

代码实现

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] result = new int[numCourses];
        for (int i = 0; i < numCourses; i++) result[i] = i;
        
        int m = prerequisites.length;
        if (m == 0) return result;
        
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[numCourses];
        int[] inDegree = new int[numCourses];
        List<List<Integer>> edges = new ArrayList<>();
        
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        
        for (int i = 0; i < m; i++) {
            edges.get(prerequisites[i][prerequisites[i].length - 1]).add(prerequisites[i][0]);
            inDegree[prerequisites[i][0]]++;
        }
        
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                visited[i] = true;
                queue.add(i);
            }
        }
        
        int count = 0;
        while (!queue.isEmpty()) {
            int tmp = queue.poll();
            result[count++] = tmp;
            
            for (int neighbor : edges.get(tmp)) {
                inDegree[neighbor]--;
            }
            
            for (int i = 0; i < numCourses; i++) {
                if (inDegree[i] == 0 && !visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
        
        return count != numCourses ? new int[0] : result;
    }
}

四、LCR 114. 火星词典

这是一道字符串处理的拓扑排序变体。通过对比相邻单词，推导出字符间的优先级关系，进而构建图并排序。

解题思路

1. 建图：两层循环对比相邻字符串，找到第一个不同的字符，前者指向后者。
2. 合法性检查：如果一个长字符串以短字符串开头且排在前面（如 "abc" 在 "ab" 前），则非法。
3. 拓扑排序：对字符图执行 BFS，若结果长度不足则说明存在环。

代码实现

class Solution {
    Map<Character, Set<Character>> edges = new HashMap<>();
    Map<Character, Integer> inDegree = new HashMap<>();
    boolean flag;

    public String alienOrder(String[] words) {
        // 初始化入度
        for (String s : words) {
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                inDegree.put(ch, 0);
            }
        }

        // 建图
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                add(words[i], words[j]);
                if (flag) return "";
            }
        }

        // 拓扑排序初始化
        Queue<Character> queue = new LinkedList<>();
        for (char ch : inDegree.keySet()) {
            if (inDegree.get(ch) == 0) queue.add(ch);
        }

        // BFS
        StringBuffer ret = new StringBuffer();
        while (!queue.isEmpty()) {
            char tmp = queue.poll();
            ret.append(tmp);
            if (!edges.containsKey(tmp)) continue;
            for (char ch : edges.get(tmp)) {
                inDegree.put(ch, inDegree.get(ch) - 1);
                if (inDegree.get(ch) == 0) queue.add(ch);
            }
        }

        // 检查是否有剩余入度不为 0 的点
        for (char ch : inDegree.keySet()) {
            if (inDegree.get(ch) != 0) return "";
        }
        return ret.toString();
    }

    private void add(String a, String b) {
        int i = 0;
        int n = Math.min(a.length(), b.length());
        for (; i < n; i++) {
            char ch1 = a.charAt(i);
            char ch2 = b.charAt(i);
            if (ch1 != ch2) {
                if (!edges.containsKey(ch1)) edges.put(ch1, new HashSet<>());
                if (!edges.get(ch1).contains(ch2)) {
                    edges.get(ch1).add(ch2);
                    inDegree.put(ch2, inDegree.get(ch2) + 1);
                }
                break;
            }
        }
        // 检查非法情况：例如 "abc" 在 "ab" 前面
        if (i == b.length() && a.length() > i) flag = true;
    }
}