有向无环图

有向无环图 (Directed Acyclic Graph, DAG) 指的是从点出发用有方向的箭头连接到其他的点构成的整个图，而且从任意点出发，不会回到自己本身 (无环)。

前面的文章所使用的各种流程图的表达，都有使用到有向无环图，比方说 PERT 图、CPM 图就是有向无环图。

有向无环图有很多种排列显示的方式，比方说常见的这种是一般的有向无环图画法:

按照顺序连接不同的点，也可以分出来，排法位置没有很固定。

事实上之前的文章在介绍【有限状态过程】，并不是一个 DAG，主要的原因是因为流程图已经构成一个循环，会在後面的状态回到自己，如下图:

拓朴排序

拓朴排序，对於 DAG 来说，DAG 必有存在拓朴排序，若且唯若一个拓朴排序也是一个 DAG。

要展现【拓朴排序】的画法，就需要让箭头被连结出去的数字呈现大小关系，下一项要大於前一项，然後画出箭头指向，假设以修课的范例来说，

假设三个课程模组: 0,1,2 以及 3 以及 4,5 ，有预备先修的课程关系: 要修 3 的话要先过 1，要修 4 的话要先过 2 ，这样的修课关系可以变成像是下图:

完全打平的结构，似乎较能呈现拓朴排序後直觉的结果。

其他有向无环图结构

有向无环图也可以用来表示树的结构 (二元树、多重树)

另外参考到 [2] 的范例图中也用了有向无环图来表示数字的整除关系，叫做哈斯图:

从一个只有 { 1, 2, 3, 4, 5, 6, 9, 10, 15 } 的集合中，要找出他们之前被整除的关系，这里被 1 连结的，代表他们只能被 1 整除，前面的其他元素都无法整除他，也就呈现了质数的关系；

而後续的元素 4, 6, 9, 10, 15 都可以各自被 1 所连结到的元素整除，以此类推，这样就构成了一个哈斯图，哈斯图的详细应用及作法可以参考 [3]。

有向无环图可以出现在任何地方，流程图、区块链 [4][5]、演算法、数学图论，本篇文章也把几个过去使用到有向无环图都拿出来回顾了。

References:
[1] https://web.ntnu.edu.tw/~algo/DirectedAcyclicGraph.html
[2] https://zh.wikipedia.org/wiki/%E5%93%88%E6%96%AF%E5%9C%96
[3] https://blog.csdn.net/shulianghan/article/details/109061220
[4] https://www.chainnews.com/zh-hant/articles/767903222939.htm
[5] https://www.8btc.com/media/523587