Question

Directed Acyclic Graph（DAG）

没有环、无向图，就是先前提到的“树”、“森林”；没有环、有向图，就是现在提到的“有向无环图”。由于英文名称很长，所以大家习惯採用缩写“DAG”，字母皆大写。

先前我们用延伸拓展的观点来看待 Tree；同样地，我们也可以用延伸拓展的观点来看待 DAG。

DAG 没有环，不走回头路、永远不回头、不断向前进。DAG 可以重新绘制，让所有边朝著同一个方向延伸拓展、让所有点有著先后次序。

在各式各样的图之中，Tree 与 DAG 是十分重要的特例，往往存在速度极快的演算法。由于 Tree 和 DAG 没有环、方向明确，所以我们很容易安排出一个计算顺序（一般是採用拓扑顺序），循序渐进求得答案，不必受到环的折腾。

现实生活当中的 DAG

不断前进、不会后退，有时分化、有时聚合，就是 DAG 的最佳写照。

是 DAG：课程挡修规则、族谱、水系、闪电、洗澡。

非 DAG：道路交通、食物链、人体血脉、山脉、气流。

以时间轴当作主角，缘起缘灭、缘聚缘散，凡事都是 DAG。

UVa 925

Topological Ordering

楔子

在枚举所有排列的问题之中，如果我们另外再限制谁要排在谁前方、谁要排在谁后方，那麽在这些限制之下，合理的排列还会剩下哪些呢？

【注：枚举所有排列，读者们可另行参考“ Enumerate Permutations ”一文。】

先后限制与图

谁要排在谁前方、谁要排在谁后方，其实就是两两之间的关係，故可以改用图来表示：把图上一条由 A 点连向 B 点的边，想成是 A 必须排在 B 前方（B 必须排在 A 后方）。

当然啦，也可以把图上一条由 A 点连向 B 点的边，想成是 A 必须排在 B 后方。不过一般来说我们习惯成自然地使用前者。

Topological Sort 与 Topological Ordering

“拓扑排序”是排序一张有向图的点的方式。把图上一条由 A 点连向 B 点的边，想成是 A 必须排在 B 前方（B 必须排在 A 后方）。“拓扑排序”用来找出合理的排列顺序，让每一个点的先后顺序，符合每一条边所规定的先后顺序。

“拓扑顺序”是指一张有向图经过“拓扑排序”后，每一个点的先后顺序。一张图有许多种“拓扑顺序”。只要不违背图上每一条边的先后规定，要怎麽排列图上的点都行。

图上不能有环

当图上有环，拓朴顺序就不存在。因为环上每一个点都会有连向自己的边，意味著环上每一个点必须排在其他点的后方，环上每一个点都不能在排列顺序中拔得头筹，所以合理的排列顺序不存在。

找出一个合理的排列顺序（Kahn's Algorithm）

要找出合理的排列顺序，首先得决定第一点！知道如何找出第一点，那麽就可以循序渐进的再找出第二点、第三点了。

可以作为第一点的点，想必它不必排在其他点后方。也就是说，没有被任何边连向的点，就可以作为第一点。如果有很多个第一点，那麽找哪一点都行。

决定第一点之后，那麽剩下所有点都会在第一点后方。所有关于第一点的先后规定，都已经符合了，规定存不存在都无所谓。因此，决定第一点之后，就可以删去此点，以及删去由此点连出去的边──原问题可以递迴地缩小！

只要反覆寻找没有被任何边连向的点，然后删去此点以及删去由此点连出去的边，就可以找出一个合理的排列顺序了。

附带一提，要找出合理的排列顺序，也可以由最后一点开始决定！无论要从第一点找到最后一点，或是从最后一点找到第一点，都是可以的。各位可以想想看该怎麽做。

儘管这个问题有递迴的性质，可以用递迴语法来实作，但由于递迴的分支只有一条，故亦可以用迴圈语法。我想大家都会选择以比较简单的迴圈语法来实作吧？

实作时，可以利用变数记录图上每一个点目前仍被多少条边连到。寻找没有被任何边连向的点，就直接看该变数是不是零；删去由此点连出去的边，就顺便更新变数的值。

Lowest Common Ancestor

Depth

DAG 可以仿照 Tree 来定义“深度”：一张有向无环图，每个点的“深度”，就是起点到每个点的最远距离。

DAG 的起点和终点有许多个，抵达一个点的路线有许多条。DAG 的“深度”也就是边数最多的那一条路线的边数（即 Longest Path 的长度）。

利用拓朴顺序、取最大值，就可求得各点的深度。

应该也有最近距离的版本，但是我不知道专有名词是什麽。

Lowest Common Ancestor

DAG 可以仿照 Tree 来定义“最低共同祖先”：一张有向无环图，图上两点的共同祖先当中，离起点最远、深度最深的那一个共同祖先。

Tree 只有唯一一个 LCA；DAG 可能有许多个 LCA、也可能没半个。

如果定义成最近距离，会产生什麽问题呢？留给读者想想看。

演算法

求出有向无环图上所有点对的 LCA。

一、每个点，求深度：拓朴顺序、取最大值。
二、每个点，找出祖先们：每个点，作为起点，逆向 Graph Traversal。
三、每个点对，找出 LCA：穷举共同祖先，深度最深的共同祖先就是 LCA。

时间複杂度分成三部份讨论：

一、一次 Graph Traversal 的时间。

二、V 次 Graph Traversal 的时间。图的资料结构为 adjacency matrix，时间複杂度为 O(V^3)；图的资料结构为 adjacency list，时间複杂度为 O(V*(V+E))，或者简单写作 O(VE)。

三、求出一个点对的 LCA 需时 O(V)，总共 O(V^2) 个点对，时间複杂度为 O(V^3)。

总时间複杂度为 O(V^3)。

UVa 11457

演算法

http://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/LCA-Max-witness.pdf

时间複杂度为 O(VE)。