您当前位置: 首页> 资讯> 一份关于有向无环图DAG的用途待接收!

热门标签

热门动态

一份关于有向无环图DAG的用途待接收!

作者:链大全 日期:2018-10-22 17:52:36


有向无环图(DAG, Directed Acyclic Graph):是一个无回路的有向图。如果有一个图,从A点出发到B点,然后经过C点,最后可以顺着方向回到A,形成闭环,那么这个图就不是非向无环图。如果将从C到A的边方向改为从A到C,则变成有向无环图。如图1和图2。

 

图1

 

图2

 

看上面这两幅图,应该可以明白了,当然这个图是很简单的,只有三个点,事实上可能是由百万千万或者更多个点组成的图。有向无环图就是从一个图中的任何一个点出发,不管走过多少个分叉路口,都没有回到原来这个点的可能性。

 

拓扑排序:就是一个有向无环图的所有定点的线性序列。且这个序列必须满足这两个条件:

 

· 每个顶点出现且只出现一次;


· 如果在图中,有一条从A点到B点的路线,那么在拓扑排序中,点A一定排在点B的前面。

 

这个东西,是比较难理解。比如在这个有向无环图中,它用拓扑排序,该怎么进行呢?

 

先找一个起点,很明显,这个起点就是1号点了,因为这个点,没有任何其他指向它的路线;然后将这个起点删除,并同时删除这个起点发射出去的路线;

 

重复上面两个步骤,知道这张有向无环图的所有点都被删除干净;

 

如果到某个阶段,发现当前图中不存在像1号点这样的起点了,那么这张图就不是有向无环图了。

 

最后,一个完整的拓扑排序就完成了,结果为:1、2、4、3、5。

 

从上面这张图中,可以看到DAG的每一个节点都可以向下连接任意多个新的节点,这个有什么用呢?如果在这一个区块内部交易数据或者与之相连的下一步的交易数据也是过多的话,那么就可以分成足够多个区块来共同分担区块压力,从而可以提高交易的吞吐量。相比于比特币这样的系统每次只能打包一个区块来说,简直是完胜。

 

存在的弊端

 

没有一个东西是完美的,有优势就有缺点,所以DAG的缺点目前在安全问题上面,主要是双花和影子链攻击。这个问题后续将会继续分析。