前言

拓扑排序需要一个容器装入度为0的节点，需要去掉该节点以及相关的边，顺便修改度，再把度边为0的节点进入容器。容器的选择可以是栈，也可以是队列进行层次遍历。

一、课程表II

二、邻接表+入度数组+层序遍历

package everyday.dfs;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
// 课程表II
public class FindOrder {
/*
构建邻接矩阵 + 度数组 + 任意一个拓扑排序。
*/
public int[] findOrder(int numCourses, int[][] prerequisites) {
// 初始化邻接表 + 入度数组。
init(numCourses);
// 为邻接表 + 入度数组进行赋值。
for (int[] prerequisite : prerequisites) {
addEdge(prerequisite[0], prerequisite[1]);
inDegree[prerequisite[0]]++;
}
// 拓扑排序
return order();
}
private int[] order() {
// 路径容器。
List<Integer> rs = new ArrayList<>();
// 收集起点，即入度为0的节点。
Queue<Integer> que = new LinkedList<>();
for (int i = 0; i < inDegree.length; i++) {
if (inDegree[i] == 0) que.add(i);
}
// 拓扑排序。
int count = 0;
while (!que.isEmpty()) {
Integer node = que.poll();
rs.add(node);
// bug1：加入节点，就必须马上计数，下面有continue，不能放在末尾。
count++;
// 更新度。
List<Integer> next = graph[node];
if (next == null) continue;
for (int n : next) {
if (--inDegree[n] == 0) que.add(n);
}
}
if (count != inDegree.length) return new int[]{};
int[] ans = new int[rs.size()];
for (int i = 0; i < rs.size(); i++) ans[i] = rs.get(i);
return ans;
}
// 构建邻接表
private void addEdge(int behind, int front) {
addNode(behind);
addNode(front);
graph[front].add(behind);
}
private void addNode(int node) {
if (graph[node] == null) graph[node] = new ArrayList<Integer>();
}
private void init(int numCourses) {
graph = new List[numCourses];
inDegree = new int[numCourses];
}
// 度数组 + 邻接表
List[] graph;
int[] inDegree;
}

总结

1）拓扑排序 = 邻接表（List数组 || Map）+ 入度数组 + 容器（队列 || 栈）。

参考文献

[1] LeetCode 课程表II

最后

以上就是过时墨镜为你收集整理的课程表II [邻接表 + 度数组 + 层序遍历 = 拓扑排序]前言一、课程表II二、邻接表+入度数组+层序遍历总结参考文献的全部内容，希望文章能够帮你解决课程表II [邻接表 + 度数组 + 层序遍历 = 拓扑排序]前言一、课程表II二、邻接表+入度数组+层序遍历总结参考文献所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。