算法专题:拓扑排序
拓扑排序(Topological Sorting)是图论中一个比较重要的概念。它主要用来解决下面这类问题: 给定一个 AOV 网(Activity On Vertex Network), $ A\rightarrow B $ 表示活动 $ A $ 必须在活动 $ B $ 之前完成。请给出一个合理的活动顺序。 当然,AOV 网中不可能出现环,因为出现了环就无法拓扑排序。因此可以用拓扑排序来判断图中是否存在环。 关于拓扑排序,我们来看一下下面这张图片: Toplogical Sorting 我们可以用队列来实现这个算法,具体改进的过程如下: 记录每个点的入度; 将入度为 0 的顶点加入队列; 依次对入度为 0 的点进行删边操作,同...