咕了这么久终于更新了
简介
拓扑排序(topological sort),是图论中的一种算法,简单点说就是:
对一个有向无环图(DAG)的节点进行线性排序,使得从点$u$到点$v$的每个有向边$uv$,$u$都在$v$之前。
当且仅当图没有环,即有向无环图时,该图存在拓扑排序。因此,拓扑排序可以用于判断图是否存在环。
可以形象地解释为:
在某校中,每门课可能有若干门先修课,如果要修读某一门课,则必须要先修读此课程所要求的先修课后才能修读。假设一个学生同时只能修读一门课程,那么,他修完所有课程的顺序是一个拓扑序。
举个栗子:
对于下图,拓扑排序的结果是$1 - 6 - 3 - 4 - 2 - 5$。
当然,拓扑排序的结果肯定是不唯一的,比如图片中$6 - 1 - 4 - 3 - 5 - 2$的顺序显然也可以。