拓扑排序

拓扑排序:从某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。

AOV-网,用顶点表示活动,用弧表示活动间的优先关系的有向图,不应该出现有向环,存在有向环意味着某项活动应以自己为先决条件,这是荒谬的。

记住三句话:

1.从有向图中选择一个入度为0的点输出

2.删除1中的顶点,并删除从该顶点出发的全部边

3.重复上述两步,直到剩余的图中不存在入度为0的顶点为止

代码实现时,用顶点出栈表示将这个顶点删去,因为只要将这个顶点出栈就代表它将不会参与后续的拓扑排序了

对有n个顶点和e条弧的有向图而言,建立求各顶点的入度的时间复杂度为O(e);建零入度顶点栈的时间复杂度为O(n);在排序过程中,while循环执行了e次;总的时间复杂度为O(n+e)

原文地址:https://www.cnblogs.com/Liu269393/p/10226292.html