注意:
① 若将图中顶点按拓扑次序排成一行,则图中所有的有向边均是从左指向右的。
② 若图中存在有向环,则不可能使顶点满足拓扑次序。
③ 一个 DAG 的拓扑序列通常表示某种方案切实可行。
【例】一本书的作者将书本中的各章节学习作为顶点,各章节的先学后修关系作为边,构
成一个有向图。按有向图的拓扑次序安排章节,才能保证读者在学习某章节时,其预备知
识已在前面的章节里介绍过。
④ 一个 DAG 可能有多个拓扑序列。
【例】对图 G9 进行拓扑排序,至少可得到如下的两个(实际远不止两个)拓扑序列:
C0,C1,C2,C4,C3,C5,C7,
C8,C6 和 C0,C7,C9,C1,C4,C2,C3,C6,C5。
⑤ 当有向图中存在有向环时,拓扑序列不存在
【例】下面(a)图中的有向环重排后如(b)所示,有向边<v3,vl>和其它边反向。若有向图被
用来表示某项工程实施方案或某项工作计划,则找不到该图的拓扑序列 (即含有向环),就