前言：
在实际工作场景中用到了拓扑排序，遂记录下来以供参考理解。
拓扑排序介绍：
首先，拓扑排序区别于一般的数值类排序算法，如冒泡排序、快速排序、堆排序等。它的处理对象是有向无环图DAG，最终是把有向无环图转换成一个有顺序的列表。
拓扑排序实际应用场景：
在实际应用场景中，需要对数据进行一个ETL处理，具体处理流程类似下图：
由于在ETL过程中存在流程的依赖顺序关系，如“数据join操作2”执行前必须要先进行第一次数据join操作和接入数据表C，否则ETL流程不成功，由此在实际执行过程中就需要对此类流程图进行排序，最终将其转换为从左到右的顺序正常执行。
那么在排序过程中本质上就是一个拓扑排序，把每一个流程处理框看成一个顶点，流程框之间有向连接线作为顶点之间的边。按照其拓扑排序后，结果可能是1--2--3--4--5--6，或者是2--1--3--4--5--6，或者是2--1--4--3--5--6等共计6种排序结果。
最终的顺序取决于实际算法中用到的排序方法，但是无论是以上罗列出的哪种顺序，都能保证整个流程可以正常的执行。
拓扑排序实现原理：
0.定义一个最终结果List集合resultList；
1.将上述一个流程实际节点的属性集合定义为一个java类DefinedNode（其中包含该节点依赖的下一个节点集合，该节点入度，节点业务特有的属性）；
2.每个节点都有一个唯一id，并用NodeMap来存储整个流程每个节点的数据，存储数据为<nodeId,DefinedNode>；
3.遍历map集合，找出节点中入度为0（即没有被依赖）的节点放入栈stack中；
4.遍历栈中元素，取出栈元素添加到resultList集合中，找到和它有关联的节点并将其关联的节点入度减1；
5.其关联的节点如果减1后入度为0，则添加到栈stack中；
6.重复4.5步，直到栈中不存在元素为止；
此时，返回的resultList集合就是排序后结果，此时resultList中集合对象可能为④--②--①--③--⑤--⑥，即整个流程最终按照resultList中对象顺序执行。
由于具体业务场景各有不同，在此仅写一个通用的用例来说明。
public class DAGSortTest {static class DefinedNode{int id;//节点idint inValue;//节点入度值List<Integer> nextIds;//下一个节点id集合public DefinedNode(int id, int inValue, List<Integer> nextIds) {this.id = id;this.inValue = inValue;this.nextIds = nextIds;}public int getId() {return id;}public int getInValue() {return inValue;}public List<Integer> getNextIds() {return nextIds;}}public static void main(String[] args) {Map<Integer, DefinedNode> nodeMaps = initDefinedNodeMap();List<DefinedNode> resultList = DagSort(nodeMaps);for (DefinedNode definedNode : resultList) {System.out.println(definedNode.getId());}}private static Map<Integer, DefinedNode> initDefinedNodeMap() {Map<Integer, DefinedNode> nodeMaps = new HashMap<>();List<Integer> nextIds1 = new ArrayList<>();nextIds1.add(3);DefinedNode node1 = new DefinedNode(1,0,nextIds1);nodeMaps.put(1,node1);List<Integer> nextIds2 = new ArrayList<>();nextIds2.add(3);DefinedNode node2 = new DefinedNode(2,0,nextIds2);nodeMaps.put(2,node2);List<Integer> nextIds3 = new ArrayList<>();nextIds3.add(5);DefinedNode node3 = new DefinedNode(3,2,nextIds3);nodeMaps.put(3,node3);List<Integer> nextIds4 = new ArrayList<>();nextIds4.add(5);DefinedNode node4 = new DefinedNode(4,0,nextIds4);nodeMaps.put(4,node4);List<Integer> nextIds5 = new ArrayList<>();nextIds5.add(6);DefinedNode node5 = new DefinedNode(5,2,nextIds5);nodeMaps.put(5,node5);List<Integer> nextIds6 = new ArrayList<>();DefinedNode node6 = new DefinedNode(6,1,nextIds6);nodeMaps.put(6,node6);return nodeMaps;}public static List<DefinedNode> DagSort(Map<Integer,DefinedNode> nodeMaps){List<DefinedNode> resultList = new ArrayList<>();Stack<DefinedNode> stack = new Stack();for (DefinedNode definedNode : nodeMaps.values()) {if (definedNode.getInValue()==0){stack.push(definedNode);}}while (!stack.empty()){DefinedNode definedNode = stack.pop();resultList.add(definedNode);List<Integer> nextIds = definedNode.getNextIds();for (Integer nextId : nextIds) {DefinedNode nextNode = nodeMaps.get(nextId);if (nextNode.getInValue()-1==0){stack.push(nextNode);}else {nodeMaps.put(nextNode.getId(),new DefinedNode(nextNode.getId(),nextNode.getInValue()-1,nextNode.getNextIds()));}}}return resultList;}}
最终运行结果如下：
