拓扑排序

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

举个例子，比如，我们在选修某些课程之前需要一些先修课程

我们需要学习课程 A、B，才能学习 C

那么我们可以按照A->B->C或B->A->C的过程进行学习，即学习 C 之前必须学习 A 和 B

思考

对于如下有向无环图，我们应该怎样得到它的拓扑排序呢？

我们知道若学一门课程前已经没有其他课程还需要学习，那么我们就可以学习这门课程

观察图片可以知道，课程 A 和 B 可以学习

那么我们挑选 A 和 B 后，则可知课程 C 已经没有了先修课程

然后学完 C 之后，课程 D 又可以学习了 …

这样子我们就可以在学完这门课程后，拿掉它指向其他节点的边，然后找到一个入度为 0 的节点，则此节点为下一个可以摘除的节点，不断循环此过程，我们就可以得到有向无环图的拓扑排序了

代码实现

对于拓扑排序，最重要的就是记录每一个节点的入度

我们利用inDegree数组去记录节点 iii 的入度，为inDegree[i]

构建图时，节点 x 指向 y，则 y 的入度加 1

for (int i = 0; i < m; i++) {int x = sc.nextInt();int y = sc.nextInt();link[x].add(y);inDegree[y]++;}

一个时刻可能有多个节点的入度为 0，则我们利用队列去存储

初始时，我们将入度为 0 的节点加入队列

for (int i = 0; i < n; i++) {if (inDegree[i] == 0)queue.add(i);}

当移除当前节点时，需要将当前节点指向的节点入度减 1，如果指向的节点入度减为 0，则将其加入队列

for (int i = 0; i < link[cur].size(); i++) {int v = link[cur].get(i);if (--inDegree[v] == 0)queue.add(v);}

接下来就可以得到完整的代码了

import java.util.*;public class Main {static int MAX_N = 10000;static int[] inDegree = new int[MAX_N];static List<Integer>[] link = new ArrayList[MAX_N];static int n, m;static List<Integer> topologicalSort() {List<Integer> res = new ArrayList<>();Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < n; i++)if (inDegree[i] == 0)queue.add(i);while (!queue.isEmpty()) {int cur = queue.poll();res.add(cur);cur = -1;for (int i = 0; i < link[cur].size(); i++) {int v = link[cur].get(i);if (--inDegree[v] == 0)queue.add(v);}}// 若排序后节点小于 n，说明存在环return res.size() == n ? res : null;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();for (int i = 0; i < n; i++)link[i] = new ArrayList<>();m = sc.nextInt();for (int i = 0; i < m; i++) {int x = sc.nextInt();int y = sc.nextInt();link[x].add(y);inDegree[y]++;}List<Integer> ans = topologicalSort();if (ans == null)System.out.println(-1);else ans.forEach(System.out::println);}}