提示： top 音译成 拓扑，所以是一个意思

活动图（AOV网）

在有向图中，用顶点表示 活动，用有向边表示 活动之间的优先关系（先后关系），则称这样的有向图为活动图，简称AOV网。

top序列（先后序列）

按照 箭头方向 把有向图的节点连起来就会形成一个序列。如果该序列没有违反途 中节点的先后顺序，就叫做top序列，也就是先后序列。

上图的拓扑序列有多个：

• 因为顶点 0 指向 2 和 1，所以序列中第2个、第3个元素可以是 2 或 1

• 因为顶点 4 指向 3，1 指向 3，所以第4个元素是 4，第5个元素是 3

• 因为顶点 3 指向 5，4 指向 6，所以第6个、第7个元素可以是 5 或 6

• 最后一个元素是 7

序列如下：

• 02143567
• 01243657
• 02143657
• 01243567

结论

• 如果图中顶点 i -> j，那么 top序列中，i 一定在 j 前面

• 如果top序列中，i 在 j 前面，那么图中不可能有边从顶点 j 指向顶点 i

应用场景

对 施工的流程图具有特别重要的作用，它可以决定哪些子工程必须要先执行，哪些子工程要在某些工程执行后才可以执行。

为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个 有向图 来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行

参考：
https://blog.csdn.net/qq_35644234/article/details/60578189

题

拓扑序列是有向无环图中所有顶点的一个线性序列，若有向图中存在弧 <V，W> 或存在从顶点 v 到 w 的路径，则在该有向图的任一拓扑序列中，v 一定在 w 之前。下面有向图的拓扑序列是( )

A、41235
B、43125
C、42135
D、41325

分析

技巧：可通过反向查找是否违法

如：选项C中，按照下面步骤判断：

1. 第2个元素 2 没有指向 第1个元素 1 的边，合法
2. 第3个元素 1 有指向 第2个元素 2 的边，违法，所以是 错的

答案

A

题

对有向图 G 进行拓扑序列得到的拓扑序列中，顶点 Vi 在顶点 Vj 之前，则说明G中( )

A、一定存在有向弧 <Vi, Vj>
B、一定不存在有向弧 <Vj, Vi>
C、必定存在从 Vi 到 Vj 的路径
D、必定存在从 Vj 到 Vi 的路径

分析

选项A，错误，只能说明 顶点 Vi 在 Vj 之前，但不一定有边
选项B，正确
选项C，错误，只能说明 顶点 Vi 在 Vj 之前，不一定存在路径
选项D，错误，顶点 Vi 在 Vj 之前

答案

B