(太蒻了
拓扑排序(看文章之后可能不能被称作排序),是对有向无环图所有顶点的线性排列.
举个栗子:
图 \(G\) \(=\) \(1\) ---> \(2\) ---> \(3\)
此时观察该图,其中只有点 \(1\) 没有入度,因此删除点 \(1\) 及其所有的边,将点 \(1\) 加入集合 \(V\) 中.
然后继续观察该图,现在点 \(2\) 没有入度,删除点 \(2\) 及其所有的边,将点 \(2\) 加入集合 \(V\).
最后删除点 \(3\) ,加入集合 \(V\) ,此时 \(V\) \(=\) \(\{1,2,3\}\) .
这就是对有向无环图 \(G\) 的拓扑排序.