拓扑排序序列怎么写拓扑排序序列怎么写出来-亚博安卓下载

由aov网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。

(1) 选择一个入度为0的顶点并输出之；

(2) 从网中删除此顶点及所有出边。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

拓扑排序是一种数学原理，逆拓扑排序也是一种数学原理，二者相互联系，但原理上并不相反，只是在数学科学中的两种理论。

首先，拓扑排序是指对于一个有向无环图g，将g中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若 ∈e(g)，则u在线性序列中出现在v之前。那么，假设存在回路，v1,v2,v3,……,vn，v1，则边∈e(g)，故v1在v2之前，类似地，v2在v3之前，……，因此，得出，v1在vn之前。

又因为∈e(g)，即vn在v1之前。相互矛盾，所以假设不成立。所以，一个图能够进行拓扑排序的一个必要条件就是图中不存在环。

拓扑排序的基本思想

1. 定义一个队列和一个hashmap（hashmap用来存储node节点和该节点入度的值）；

2. 遍历所有的节点，把所有的节点的入度和node值存放到hashmap中去，并将入度为0的节点存放到队列queue中去；

3.定义一个list数组，用来存放node，并作为最后的节点输出；

4. 取出队列中的一个元素，并将该元素添加到result数组中；

5. 遍历上面取出的元素的next节点，将其所有next节点的入度都-1 如果有一些节点的入度变为0时，把他们放进去队列queue里面；而如果上面取出的元素没有next的话，继续从队列queue中poll（）出新的元素。

拓扑排序解决的是依赖图问题。

依赖图表示的是节点的关系是有依赖性的，比如你要做事件 a，前提是你已经做了事件 b。除了 “先有鸡还是先有蛋” 这类问题，一般来说事件的依赖关系是单向的，因此我们都用有向无环图来表示依赖关系。

拓扑排序就是根据这些依赖来给出一个做事情，或者是事件的一个顺序。