用有向图表示依赖
若任务 必须先于任务 ,便画箭头 。拓扑次序是一个把每个顶点列出一次的列表,并对每条箭头都把 放在 前面。有向环使这种次序不可能存在:沿环的箭头会要求某顶点排在自身之前。
假设图是有限有向多重图,有 个顶点及 条有向边。平行箭头须分别计算,自环也是有向环。我们只研究先后关系:拓扑次序本身不是考虑工期、资源限制或最短完成时间的排程。空图的次序是空列表。
定义 4.3.1
(拓扑次序与有向环)
设 是顶点集为 的有限有向多重图。
- 的拓扑次序是列表 : 中每个顶点恰出现一次,且对每条有向边 ,顶点 都出现在 之前。
- 有向环是一列边 ,其中 。当 时它是自环。
- 若 没有有向环,就称 无环。
移除没有剩余前驱的顶点
对每个顶点,维护尚未移除的顶点所诱导子图中的入度。起初把所有入度为零的顶点放进队列。反复从队列移除一个顶点、把它加入输出,并对其每条出边,把目的顶点的剩余入度减一。当尚存目的顶点的入度降为零,便加入队列;队列为空时停止。
定理 4.3.2
(次序或有向环证书)
算法输出全部顶点,当且仅当图中没有有向环。若全部顶点均输出,其输出次序就是拓扑次序;若提前停止,剩余子图必含有向环。
证明
(计数器、输出次序与卡住的顶点集)
顶点从队列取出后称为已移除;顶点 的计数器是从未移除顶点指向 的边数(计重数)。起初没有顶点被移除,各计数器就是入度。移除 时,每条边 使 的计数器减一次,所以计数器保持精确。顶点恰在计数器降为零(或起初为零)时进入队列;计数器从不增加,因此每个顶点至多入队一次,也就至多输出一次。
次序。顶点 只在计数器为零时入队,也就是它的所有前驱都已移除,而且在 被移除前计数器一直为零。所以输出顶点之间的每条边 , 都先于 输出。若全部顶点都输出,输出就是拓扑次序。
提前停止。设队列已空,而未输出顶点集 非空。 中计数器为零的顶点本会入队并被移除,所以 中每个顶点的计数器为正:它有一条来自 中顶点的入边。从任一 出发,取 使 ,再取 使 ,依此类推。 有限,故有顶点重复,设 ,。把边 连起来便是 内的有向环。
有环则不能完整输出。若全部顶点都输出,输出便是拓扑次序,于是有向环 的顶点位置须满足 ,这不可能( 时即 )。因此算法输出全部顶点,当且仅当 无环。
证明透视
不变量与有限性用在哪里
这个证明分两半,用到不同的事实。次序的论证与卡住顶点集的论证都建立在同一个不变量上:顶点的计数器等于它剩余入边的条数,并且按边计算。这个等式是算法状态(队列为空)与图结构(每个剩余顶点都有剩余前驱)之间唯一的桥梁。“有环则不能完整输出”这一半完全没有用到算法,只用到拓扑次序的定义。
不显然的一步是在卡住的顶点集内沿前驱向后追踪。它必然终止,因为集合有限;在无限图上,例如整数集配边 ,每个顶点都有前驱,却没有环。重复的顶点把追踪路径封闭成环。追踪不必从环上开始:起点可以在环的下游,只有重复的那一段才是环。
要在提前停止后给出具体见证,可以扫描剩余图的边,为每个剩余顶点记录一个剩余前驱。沿前驱指针走至顶点重复,再反转重复的指针序列,便列出有向环。自环给出一条边的见证。这次额外扫描与遍历需 时间。
命题 4.3.3
(线性运行时间)
使用邻接表时,算法需 次运算及 辅助空间(不计输入图与输出列表)。
证明
(每个顶点与每条边只处理一次)
计算全部入度时每条边扫描一次。每个顶点至多入队一次,因此至多被移除一次,移除时其每条出边各扫描一次。总工作量是顶点的 加边的 。队列、计数器与输出各至多存放 项。
扫描例子与容易误解的剩余顶点
例题 4.3.4
(独立选择可以给出不同次序)
取顶点 ,边为 、、 和 。起初 的入度为零。若先进先出队列按此顺序开始,移除 后 会在 后进入队列,输出为 。它符合四条箭头;不同队列次序可以得到其他有效拓扑次序。
例题 4.3.5
(停止的运行与有向环见证)
取 、、、、。计数器为 、、、、。只有 入队;移除它后 降为 ,队列随即为空,输出只有 。剩余顶点是 ,为各自记录一个剩余前驱:、、、。从 出发,指针给出 , 重复。重复的部分是 ,反转指针便得有向环 。这次追踪从不在环上的 开始;而已输出的 指向环,自己却不在环上。
例题 4.3.6
(平行边与自环)
取两条平行边 及一条边 。计数器为 、、。移除 时 按每条边各减一次,共减两次而降为 ,所以 入队;移除 后 降为 。输出为 。再取只有一个顶点 并带自环 的图:它的计数器是 ,没有计数器为零的顶点,队列起初为空,输出也是空的。剩余图是 ,,指针立即重复,见证便是一条边的环 。
反例模式
剩余顶点不一定都在环上
对于 、、,没有顶点入度为零,因此三个都留下。环是 ; 在环的下游而不在任何有向环上。提前停止只证明剩余图存在环,不代表每个剩余顶点都属于环。
常见错误
常见错误
(按邻居而不是按边减少计数器)
设有两条平行边 ,且再没有其他边指向 。 的计数器起初是 。若实现对 的每个不同出邻居只减一次,计数器只降到 , 就永远不入队,算法停止时 仍留下,并在无环图上报告有环。计数器必须按边计算,所以每条出边都要减一次。
常见错误
(以为先进先出的输出就是最小次序)
先进先出队列不一定给出字典序最小次序。对于 及孤立的 ,若队列以 开始,会得到 ,但 更小。若要保证固定全序下的最小次序,需另设最小优先队列规则并分析;任意先进先出顺序没有此保证。
练习
快速检查
(对于 、、 和孤立的 ,给出一个拓扑次序。)
先找出入度为零的顶点。
解答 · 答案
一个次序是 : 均先于 ,而 先于 。
快速检查
(为何移除 时,两条平行箭头 要把入度减两次?)
把计数器和剩余图比较一下。
解答 · 答案
两条都是 的入边,移除 时两条都消失。若只减一次,计数器便与剩余图不一致。
快速检查
(对于 、、,指出一个环,以及一个不在该环但留下的顶点。)
先找出哪些顶点入度为零。
解答 · 答案
环为 ; 不在该环,但因前驱 尚在而留下。
快速检查
(自环允许拓扑次序吗?停止后算法能给出什么见证?)
想想该顶点要怎样排在自己之前。
解答 · 答案
不允许:它要求顶点先于自身。追踪其剩余前驱指针可把该自环作为有向环见证。