拓扑排序邻接表构建疑惑：course-schedule II问题方向选择

问题背景 #

我在解决LeetCode的Course Schedule II问题，题目要求根据课程依赖关系找出可行的修课顺序。例如输入依赖关系[1,0] [2,0] [3,1] [3,2]，其中[1,0]表示修读课程1前必须先完成课程0（第二个元素是第一个元素的先修课）。

解决方案采用拓扑排序，核心步骤为：

• 创建邻接表（adjacency list）
• 创建入度（indegree）数组/映射
• 从入度为0的课程开始遍历（代码中使用BFS实现）

错误的邻接表构建方式 #

我最初构建的邻接表是课程→先修课的映射：

1 -> [0]
2 -> [0]
3 -> [1, 2]

这种方式无法正常运行：入度为0的课程是0，但0没有对应的邻接映射，遍历仅执行一次就停止，无法推进后续课程的处理流程。

正确邻接表的构建逻辑与理论依据 #

正确的邻接表应该是先修课→依赖它的课程的映射：

0 -> [1, 2]
1 -> [3]
2 -> [3]

核心逻辑：拓扑排序的「依赖传递」需求 #

拓扑排序的本质是按依赖顺序输出节点，当我们处理完一个节点（比如先修课0），需要快速知道哪些节点（课程1、2）的依赖被满足了——也就是这些节点的入度可以减1，当入度减到0时，就可以加入遍历队列等待处理。

邻接表的核心作用就是：记录当前节点完成后，哪些后续节点的依赖状态需要更新。

邻接表方向的判断模板 #

判断邻接表方向可以遵循这个固定思路：

1. 明确问题中的「先后关系」：A必须在B之前完成（比如A是B的先修课）
2. 拓扑排序中，处理完A后，需要通知B：你的一个依赖已经完成
3. 因此邻接表应该建立**A → [B, C, ...]**的映射，即「前置节点→所有依赖它的后置节点」

从入度角度辅助理解：

• 入度代表节点需要满足的依赖数量（比如课程1的入度是1，代表它有1个先修课）
• 当处理完前置节点A，所有依赖A的节点的入度都要减1，这时候就需要通过邻接表快速定位这些节点

完整Java实现代码 #

public class CourseSchedule2 {

    //[0, 1], indicates that to take course 0 you have to first take course 1.
    public List<Integer> findOrder( int[][] prerequisites ){

        List<Integer> result = new ArrayList<>();

        Map<Integer, List<Integer>> adjMap = createAdjacencyList( prerequisites );
        System.out.println("Adjacency Map: " + adjMap);

        Map<Integer, Integer> indegree = createIndegree( prerequisites );
        System.out.println("Indegree: " + indegree);

        Queue<Integer> queue = new ArrayDeque<>();
        for( Map.Entry<Integer, Integer> entry : indegree.entrySet() ){
            //In-degree value of 0 means this course has no pre-req
            if( entry.getValue() == 0 ){
                queue.add( entry.getKey() );
            }
        }

        while( !queue.isEmpty() ){
            Integer course = queue.poll();
            result.add( course );

            if( adjMap.containsKey(course)){
                for( int neighbor : adjMap.get(course) ){
                    indegree.put(neighbor, indegree.get(neighbor) -1 );

                    if( indegree.get(neighbor) == 0 ){
                        queue.add(neighbor);
                    }
                }
            }
        }
        System.out.println(result);

        if( result.size() == prerequisites.length ){
            return result;
        }else {
            return Collections.emptyList();
        }
    }


    public Map<Integer, Integer> createIndegree( int[][] courses ){
        Map<Integer, Integer> indegree = new HashMap<>();

        for( int[] course : courses ){
            int courseToTake= course[0];
            int preCourse   = course[1];
            indegree.put(courseToTake, 0);
            indegree.put(preCourse, 0);
        }

        //Update indegree based on the course
        for( int[] courseEntry : courses ){
            int course = courseEntry[0];
            indegree.put(course, indegree.get(course) + 1);
        }

        return indegree;
    }


    private static Map<Integer, List<Integer>> createAdjacencyList( int[][] prerequisites ){
        Map<Integer, List<Integer>> adjMap = new HashMap<>();
        for( int[] preq : prerequisites ){
            int curCourse = preq[0];
            int preCourse = preq[1];
            adjMap.computeIfAbsent( preCourse, k -> new ArrayList<>()).add(curCourse);
        }

        return adjMap;
    }


    public static void main( String[] args ){
        CourseSchedule2 tsort = new CourseSchedule2();
        List<Integer> result = tsort.findOrder( new int[][]{ 
                {1, 0},
                {2, 0},
                {3, 1},
                {3, 2}
        });

        System.out.println("Result: " + result);
    }

}

内容的提问来源于stack exchange，提问作者CaptainHastings