拓撲排序 - Topological Sorting

上一篇講到 DAG 有向無環圖 - Directed Acyclic Graph

這篇來研究 拓撲排序 - Topological Sorting

這篇文章講得很清楚：

https://songlee24.github.io/2015/05/07/topological-sorting/

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

就是在 DAG 中找到只出不進的點，然後移除，然後再繼續找只出不進的點移除，這樣依序移除的順序就是 拓撲排序

上面的排序就是 1 -> 2 -> 4 -> 3 -> 5

一个有向无环图可以有一个或多个拓扑排序序列。