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

一、拓扑排序基础

1.1 有向无环图（DAG）

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

1.2 AOV 网：顶点活动图

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

1.3 什么是拓扑排序

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

1.4 基于 BFS 的实现思路

借助队列进行广度优先搜索（BFS）是实现拓扑排序的高效方式：

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

二、LeetCode 207. 课程表

题目要求判断是否能完成所有课程的学习。给定课程总数和先修课程关系数组，我们需要验证是否存在合法的拓扑排序。

解题思路

使用邻接表 List<List<Integer>> 表示图结构，下标对应课程 ID，数组内容指向的课程即为依赖关系。遍历先修数组构建图的同时统计每个课程的入度。随后执行一次 BFS 即可判断可行性。

注意细节：

• 每个点只能入队一次，避免重复计算。
• 若先修数组为空，直接返回 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++) {
            // 根据输入格式建立连接
            edges.get(prerequisites[i][prerequisites[i].length - 1]).add(prerequisites[i][0]);
            inDegree[prerequisites[i][0]]++;
        }
        
        // 入度为 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 的点入队
            for (int i = 0; i < numCourses; i++) {
                if (inDegree[i] == 0 && !visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
        
        // 检查是否所有点都处理过
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] != 0) return false;
        }
        return true;
    }
}

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