DAG 是有向无环图（Directed Acyclic Graph）的缩写，什么叫做有向无环呢？有向无环指的是一种有顶点和边的图结构，它可以保证从一个顶点沿着若干边前进（有向），但永远不能回到原点（无环），其结构如下图：
有向无环图这种概念，主要应用于AOV网(Activity on vertex network)和拓扑排序。
AOV网就是把所有的工程或者某种流程分为若干个小的工程或阶段，这些小的工程或阶段就称为活动。若以图中的顶点来表示活动，有向边表示活动之间的优先关系，则这样活动在顶点上的有向图称为AOV 网。在AOV 网中，若从顶点i 到顶点j 之间存在一条有向路径，称顶点i 是顶点j 的前驱，或者称顶点j 是顶点i 的后继。
AOV 网中的弧表示了活动之间存在的制约关系。例如，计算机专业的学生必须完成一系列规定的基础课和专业课才能毕业。学生按照怎样的顺序来学习这些课程呢？这个问题可以被看成是一个大的工程，其活动就是学习每一门课程。
类似的AOV 网的例子还有很多，比如大家熟悉的计算机程序，任何一个可执行程序也可以划分为若干个程序段（或若干语句），由这些程序段组成的流程图也是一个AOV 网。
那么至于拓扑排序，首先我们来复习一下离散数学中的偏序集合与全序集合两个概念。
偏序集合：若集合A 中的二元关系R 是自反的、非对称的和传递的，则R 是A 上的偏序关系。集合A 与关系R 一起称为一个偏序集合。
全序集合：若R 是集合A 上的一个偏序关系，如果对每个a、b∈A 必有aRb 或bRa ，则R 是A上的全序关系。集合A 与关系R 一起称为一个全序集合。
偏序关系经常出现在我们的日常生活中。
例如，若把A 看成一项大的工程必须完成的一批活动，则aRb 意味着活动a 必须在活动b 之前完成。比如，对于前面提到的计算机专业的学生必修的基础课与专业课，由于课程之间的先后依赖关系，某些课程必须在其它课程以前讲授，这里的aRb 就意味着课程a 必须在课程b 之前学完。
AOV 网所代表的一项工程中活动的集合显然是一个偏序集合。为了保证该项工程得以顺利完成，必须保证AOV 网中不出现回路；否则，意味着某项活动应以自身作为能否开展的先决条件，这是荒谬的。测试AOV 网是否具有回路（即是否是一个有向无环图）的方法，就是在AOV 网的偏序集合下构造一个线性序列，该线性序列具有以下性质：
1、在AOV 网中，若顶点i 优先于顶点j ，则在线性序列中顶点i 仍然优先于顶点j；
2、对于网中原来没有优先关系的顶点与顶点，如图8.33 中的C1 与C13，在线性序列中也建立一个先后关系，或者顶点i 优先于顶点j ，或者顶点j 优先于i。
满足这样性质的线性序列称为拓扑有序序列。构造拓扑序列的过程称为拓扑排序。也可以说拓扑排序就是由某个集合上的一个偏序得到该集合上的一个全序的操作。
若某个AOV 网中所有顶点都在它的拓扑序列中，则说明该AOV 网不会存在回路，这时的拓扑序列集合是AOV 网中所有活动的一个全序集合，可以得到不止一个拓扑序列。显然，对于任何一项工程中各个活动的安排，必须按拓扑有序序列中的顺序进行才是可行的。
那么，在IOTA这个项目中，提到的Tangle（缠结）就属于DAG的一种数据结构，真正意义上讲，IOTA已不属于“区块链”，你可以理解为如果比特币、以太坊使用的是底层数据结构是BlockChain，而IOTA的底层数据结构则是DAG，但它依然属于“去中心化”的范畴。
有向无环图（Tangle） 在 IOTA 里发起一笔交易的流程如下： 你需要先找到网络里的两笔交易，验证它们的合法性，然后做微量的POW计算，把自己的交易与它们绑定，再广播到网络。你的交易会被后来的交易以相同的方式验证。
如果验证你交易的其他交易越多，则你的交易的确定性越高。当达到一个临界值时，就认为这个交易被确定了，这和比特币6个区块确定交易状态的思想一致。
简单来说，IOTA是把算力作为交易的一部分。只要你想加入这个网络，那必须先成为Mini版矿工，做出微量的POW贡献，也因此它是去中心化的。 DAG的优势可以做到高并发，理论上是无限多的并发，意味着它可以大幅提升交易速度。
网友评论