作者：whisper

链接：http://proprogrammar.com:443/article/93

声明：请尊重原作者的劳动，如需转载请注明出处

    在看算法基础这本书，看到有向无环图，其中介绍到了拓扑排序，讲到了获取拓扑序列的方法，结合自己的理解，用JAVA代码实现了获取所有可能序列，水平有限，效率什么的就没有考虑，下面贴上代码：

package graphics.dag.topologicalsort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 有向无环图所有的走法
 * @author zhangxinren
 *
 */
public class TopologicalSortAll {
	// 所有的走法
	private static List<List<Integer>> result = new ArrayList<>();
	// 顶点和边的邻接表
	private static int[][] edges = {//14个顶点，索引0不用,邻接表
					{},
					{3},
					{4},
					{4,5},
					{6},
					{6},
					{7,11},
					{8},
					{13},
					{10},
					{11},
					{12},
					{13},
					{14},
					{}
				 };
	// 每条边的入度
	private static int[] inDegree;//邻接表元素个变化，inDegree初始长度也变化
	// 当前可以走的边（入度为0的边）
	private static List<Integer> next = new ArrayList<>();;
	
	public static void topologicalSort(List<Integer> oneResult, int[] inDegree, List<Integer> next){
		if(next.size() > 0){
			for(int i = 0; i < next.size(); i++){
				List<Integer> tempNext = new ArrayList<>(next);
				List<Integer> tempOneResult = new ArrayList<>(oneResult);
				tempNext.remove(next.get(i));
				tempOneResult.add(next.get(i));
				
				int[] tempInDegree = Arrays.copyOf(inDegree, inDegree.length);
				int[] tempEdges = edges[next.get(i)];
				for(int j = 0; j < tempEdges.length; j++){
					tempInDegree[tempEdges[j]]--;
					if(tempInDegree[tempEdges[j]] == 0){
						tempNext.add(tempEdges[j]);
					}
				}
				
				topologicalSort(tempOneResult, tempInDegree, tempNext);
			}
		}
		else
		{
			result.add(oneResult);
		}
	}
	
	public static void main(String[] args) {
		// 索引0不用
		inDegree = new int[15];
		
		for(int i = 0; i < inDegree.length; i++){
			inDegree[i] = 0;
		}
		
		for(int i = 1; i < edges.length; i++){
			for(int j = 0; j < edges[i].length; j++){
				inDegree[edges[i][j]]++;
			}
		}
		
		
		for(int i = 1; i < inDegree.length; i++){
			if(inDegree[i] == 0){
				next.add(i);
			}
		}
		
		topologicalSort(new ArrayList<>(), inDegree, next);
		
		for(int i = 0; i < result.size(); i++){
			for(int j = 0; j < result.get(i).size(); j++){
				System.out.print(result.get(i).get(j) + " ");
			}
			System.out.println();
		}
	}
}

    经过测试，没有发现问题，供大家参考，代码写得不好的地方还请包涵，如有不理解的地方请结合拓扑排序的相关知识加以理解。

    结果如下：

亲爱的读者：有时间可以点赞评论一下