有向无环图的所有拓扑排序
对有向无环图DAG的拓扑排序是顶点的线性排序，从而使每一有向边[u,v][u,v][u,v]，顶点u进来的顺序v在。如果图不是 DAG，则无法对图进行拓扑排序。
给定一个 DAG，打印图的所有拓扑排序。
All topological sorts of the given graph are:4 5 0 2 3 1 4 5 2 0 3 1 4 5 2 3 0 1 4 5 2 3 1 0 5 2 3 4 0 1 5 2 3 4 1 0 5 2 4 0 3 1 5 2 4 3 0 1 5 2 4 3 1 0 5 4 0 2 3 1 5 4 2 0 3 1 5 4 2 3 0 1 5 4 2 3 1 0
在有向无环图中，很多时候我们可以有彼此不相关的顶点，因此我们可以以多种方式对它们进行排序。这些不同的拓扑排序在很多情况下都很重要，例如如果顶点之间也有一些相对权重，这是最小化那么我们需要处理相对排序以及它们的相对权重，这就需要检查所有可能的拓扑排序。
我们可以通过回溯遍历所有可能的排序，算法步骤如下：
将所有顶点初始化为未访问。现在选择未访问且入度为零的顶点并将所有这些顶点的入度减少 1（对应于删除边）现在将此顶点添加到结果中并再次调用递归函数并回溯。从函数返回后，将访问、结果和入度的值重置为枚举其他可能性。
static class Graph {int V;List<Integer>[] adj;public Graph(int V) {this.V = V;adj = new LinkedList[V];for (int i = 0; i < V; i++) {adj[i] = new LinkedList<>();}}void addEdge(int u, int v) {adj[u].add(v);}void allTopologicalSortsUtil(boolean[] visited, int[] indegree, List<Integer> stack) {boolean flag = false;//标志位，表示是否所有的拓扑排序被找到与否for (int i = 0; i < V; i++) {if (!visited[i] && indegree[i] == 0) {//选择未访问过并且入度为0的顶点visited[i] = true;stack.add(i);for (int next : adj[i]) {indegree[next]--;}allTopologicalSortsUtil(visited, indegree, stack);//回溯visited[i] = false;stack.remove(stack.size() - 1);for (int next : adj[i]) {indegree[next]++;}flag = true;}}//如果找到，则打印if (!flag) {stack.forEach(i -> System.out.print(i + " "));System.out.println();}}void allTopologicalSorts() {boolean[] visited = new boolean[V];int[] indegree = new int[V];for (int i = 0; i < V; i++) {for (int x : adj[i]) {indegree[x]++;}}List<Integer> stack = new ArrayList<>();allTopologicalSortsUtil(visited, indegree, stack);}public static void main(String[] args) {// Create a graph given in the above diagramGraph graph = new Graph(6);graph.addEdge(5, 2);graph.addEdge(5, 0);graph.addEdge(4, 0);graph.addEdge(4, 1);graph.addEdge(2, 3);graph.addEdge(3, 1);System.out.println("All Topological sorts");graph.allTopologicalSorts();/*** All Topological sorts* 4 5 0 2 3 1* 4 5 2 0 3 1* 4 5 2 3 0 1* 4 5 2 3 1 0* 5 2 3 4 0 1* 5 2 3 4 1 0* 5 2 4 0 3 1* 5 2 4 3 0 1* 5 2 4 3 1 0* 5 4 0 2 3 1* 5 4 2 0 3 1* 5 4 2 3 0 1* 5 4 2 3 1 0*/}}
