跳转至

拓扑排序

  • 一个无环的有向图称为有向无环图

AOV网

  1. 用顶点表示活动，用弧表示活动之间的优先关系的有向图，称为顶点表示活动的网(Activity On Vertex Network)，即AOV网
  2. 若从顶点\(i\)到顶点\(j\)之间存在一条有向路径，则称\(i\)是\(j\)的前驱，或\(j\)是\(i\)的后继
  3. 若\(<i,j>\)是图中的弧，则称\(i\)是\(j\)的直接前驱，\(j\)是\(i\)的直接后继
  4. AOV网中不允许有环，如何判断AOV中是否有环？->拓扑排序、

拓扑排序

  1. 拓扑排序：指将AOV网中的顶点排成一个线性序列
  2. 满足：若从顶点\(i\)到顶点\(j\)有一条路径，则该序列中的顶点\(i\)一定在顶点\(j\)之前
  3. 基本思想：
    1. 选择一个无前驱的顶点并输出
    2. 从图中删除该顶点 （通过后继顶点的入度减1实现） 和该顶点的所有出发边
    3. 重复1和2，直到不存在无前驱的顶点
    4. 结论：若Counter < VertexNum，则说明图中有环
    5. 拓扑排序并不唯一

算法步骤

  1. 在数组indegree[]中存储各个顶点的入度，栈S用于临时存储入度为\(0\)的顶点
  2. if(!S.empty())
    1. 栈顶元素\(i\)出栈，并进行访问
    2. 顶点\(i\)的所有邻接点入度减\(1\)，若减去后，入度为\(0\)，则令其入栈
  3. 得出结论
  4. 排序序列即出栈序列

复杂度分析

时间复杂度

  • 求入度：\(O(e)\)
  • 度数为\(0\)的顶点入栈：\(O(n)\)
  • 若有向图无环，则每个顶点出栈后入度减1：\(O(n)\) 时间复杂度：\(O(n + e)\)

空间复杂度

逆拓扑排序

  • 与正向拓扑排序相反，操作的对象为出度为\(0\)的点

应用:

[[关键路径]]