【Java|golang】210. 课程表 II---拓扑排序

一、拓扑排序的定义：

先引用一段百度百科上对于拓扑排序的定义：

对一个有向无环图 ( Directed Acyclic Graph 简称 DAG ) G 进行拓扑排序，是将 G
中所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v ，若边 < u , v > ∈ E ( G )，则 u 在线性序列中出现在 v之前。通常，这样的线性序列称为满足拓扑次序 ( Topological Order )
的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

总结起来有三个要点：
1.有向无环图；
2.序列里的每一个点只能出现一次；
3.任何一对 u 和 v ，u 总在 v 之前（这里的两个字母分别表示的是一条线段的两个端点，u 表示起点，v 表示终点）；

二、样例：

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
示例 3：

输入：numCourses = 1, prerequisites = []
输出：[0]

提示：
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
所有[ai, bi] 互不相同

public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] inDegree=new int[numCourses];
        Map<Integer, List<Integer>> directMap = new HashMap<>();
        for (int[] prerequisite : prerequisites) {
            List<Integer> list = directMap.getOrDefault(prerequisite[1], new ArrayList<>());
            list.add(prerequisite[0]);
            directMap.put(prerequisite[1],list);
            inDegree[prerequisite[0]]++;
        }
        Queue<Integer> queue=new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
        int index=0;
        int[] res = new int[numCourses];
        while (!queue.isEmpty()){
            Integer poll = queue.poll();
            res[index++]=poll;
            List<Integer> list = directMap.getOrDefault(poll, new ArrayList<>());
            for (Integer i : list) {
                inDegree[i]--;
                if (inDegree[i]==0){
                    queue.add(i);
                }
            }
        }
        return index==numCourses?res:new int[0];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

func findOrder(numCourses int, prerequisites [][]int) []int {
	inDegree:=make([]int,numCourses)
	directMap:=make(map[int][]int,0)
	for _, v := range prerequisites {
		directMap[v[1]] = append(directMap[v[1]], v[0])
		inDegree[v[0]]++
	}
	queue:=make([]int,0)
	for i := 0; i < numCourses; i++ {
		if inDegree[i] == 0 {
			queue=append(queue, i)
		}
	}
	index:=0
	res := make([]int,numCourses)
	for len(queue)!=0 {
		poll := queue[0]
		queue=queue[1:]
		res[index]=poll
		index++
		for _,i := range directMap[poll] {
			inDegree[i]--
			if inDegree[i]==0{
				queue=append(queue, i)
			}
		}
		
	}
	if  index!=numCourses{
		return []int{}
	}
	return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33