Llf's blog

标签 拓扑排序 下的文章

February 6, 2018

拓扑排序

概念 拓扑排序是一种可以将有先决条件(即必须将a、b排在前面后再排c,缺一不可)的数据变得有序的一种排序方法。拓扑排序仅可在有向无环图中使用,同时可以判断图中是否有环。因为顺序不同,拓扑排序得到的答案可能不同。 思路 因为排序是有先决条件的,所以可以将要有先决条件的个数(在图中即为入度)记录下来,每满足一个就减一,直到个数为0便可以将其放入序列中。 手动实现 如果我们有如下的一个有向无环图,...