1、什么是拓扑排序
从给定的图的所有边中「提取出该图的某一个拓扑序列」的过程，拓扑序列是一条满足图中有向边前后关系的序列，任一有向边起点在序列中一定早于终点出现。如果图中有环，则无法提取出拓扑序列。所以拓扑排序的一个重要应用是在给定的有向图中判定是否存在环路。
总结：对图中所有的节点进行排序，要求没有一个节点指向它前面的节点。
2、拓扑排序算法的思想
入度：由其他节点指向当前节点的一条指向。
出度：由当前节点指向其他节点的一条指向。
step1：先统计所有节点的入度（即指向该节点的边的数量）
step2：首先依次输出入度为0的节点，然后把这个节点指向的节点的入度-1；
step3：循环step2，直到所有的节点被分离出来；
step4：如果最后不存在入度为0的节点，那就说明有环，不存在拓扑排序
3、拓扑排序的图示
1、首先，给定图中仅有节点 1入度为 0，我们将其加入队列。
2、我们将节点 1为起点的有向边均删掉（在图中变为橙色），更新这些有向边终点的入度，节点 2,3,4入度均减一，变为 [0,1,1]。由于节点 2的入度变为了 0，我们将其加入队列。
3、我们将节点 2为起点的有向边均删掉，更新这些有向边终点的入度，节点 3 入度减一，变为 [0]。我们将其加入队列。
4、我们将节点 3 为起点的有向边均删掉，更新这些有向边终点的入度，节点 4,5入度均减一，变为 [0,1]。由于节点 4 的入度变为了 0，我们将其加入队列。
5、我们将节点 4为起点的有向边均删掉，更新这些有向边终点的入度，节点 5 入度减一，变为[0]。由于节点 5 的入度变为了 0，我们将其加入队列。
6、我们将节点 5为起点的有向边均删掉，此时全图已经遍历完毕，没有新的节点被加入队列。
队列为空，拓扑排序结束。
4、拓扑排序算法的具体步骤
1、根据传入的二维数组以及节点数，获得每个节点的入度数量数组Inprerequisites[]，
2、得到每一个节点的后续节点集合HashSet
3、 创建一个队列， 遍历入度数量数组Inprerequisites[]，将入度数为0的节点加入队列
4、 入队完成后，开始对队列进行操作，如果队列不为空，依次将队列的元素弹出，加入最终结果集合ans，并且将弹出的元素指向的所有后继节点的入度数-1，如果其后继节点的入度数减少为0，那么也将其加入队列进行操作。
5、依次对队列元素进行弹出，直至队列为空。
6、最后输出的结果即为所有没有构成环的节点
若有收获，就点个赞吧
0 人点赞
