【图】拓扑排序（DFS和BFS解法）_任意有向图的拓扑序列可以通过dfs和bfs求解

拓扑排序

LeetCode题目：210. Course Schedule II
题目链接：https://leetcode.com/problems/course-schedule-ii/description/

题目大意：

        现在你总共有 n 门课需要选，记为 0 到 n-1。
        在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
        给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

来源：力扣（LeetCode）
中文翻译链接：https://leetcode-cn.com/problems/course-schedule-ii

解法分析

BFS

        BFS解法一般借助于队列实现，把入度为0的节点放入队列，把这个点加入到结果集中，然后把该节点指向的下一个节点入度减一，然后继续寻找入度为0的节点。
        拓展：给定每个节点的作业时间，求出平均等待时间最短的拓扑顺序。在拓扑排序的基础上，从队列取的时候，拿作业时间最短的点——用PriorityQueue实现，把Queue换成PriorityQueue。

public int[] findOrder(int numCourses, int[][] prerequisites) {
   
        // 用于存放每个节点后面的节点
        List<Integer>[] afterStudy = new List[numCourses];
        // 每个节点的入度
        int[] cnt = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
   
            afterStudy[i] = new ArrayList<>();
        }
        // 遍历加入该节点相邻的后面节点
        for (int[] prerequisite : prerequisites) {
   
            int after = prerequisite[0];
            int before = prerequisite
1
2
3
4
5
6
7
8
9
10
11
12
13
14