DAG（Directed Acyclic Graph）又稱“有向無(wú)環(huán)圖”
即是由集合的頂點(diǎn)和有向邊構(gòu)成啤斗，每條邊連接一個(gè)頂點(diǎn)到另一個(gè)，這樣崔拥，從某個(gè)頂點(diǎn)V開(kāi)始链瓦，沿著有序的邊，最終循環(huán)回再次到V是不可能的
以下是二叉樹(shù)拥峦，DAG和有向圖的區(qū)別 （摘自網(wǎng)上資源）
基于DAG數(shù)據(jù)結(jié)構(gòu)的區(qū)塊鏈網(wǎng)絡(luò)如何運(yùn)行呢？
目前采用DAG作為存儲(chǔ)結(jié)構(gòu)的代表項(xiàng)目有dagcoin、Byteball阳似、IOTA撮奏。以IOTA的底層數(shù)據(jù)結(jié)構(gòu)Tangle為例，通過(guò)節(jié)點(diǎn)發(fā)出的所有交易構(gòu)成了這個(gè)有向無(wú)環(huán)圖的集合。當(dāng)一個(gè)新的交易發(fā)生后捌年，它必須驗(yàn)證之前的兩個(gè)交易眠砾，這些驗(yàn)證關(guān)系就表示為有方向的邊褒颈。
如下圖（圖中谷丸，時(shí)間走向總是從左到右，一個(gè)小方框代表一筆交易）。
關(guān)于DAG的幾個(gè)概念：
交易的自身權(quán)重
與發(fā)送這筆交易的節(jié)點(diǎn)所投入的工作量成正比砾层。節(jié)點(diǎn)的工作量越大，這個(gè)節(jié)點(diǎn)發(fā)出交易的權(quán)重就越大
交易的累計(jì)權(quán)重
是這個(gè)交易的自身權(quán)重與直接及間接驗(yàn)證這個(gè)交易的所有交易的自身權(quán)重之和
Tip
沒(méi)有被驗(yàn)證的交易
交易的高度
從創(chuàng)世交易到當(dāng)前這個(gè)交易的最長(zhǎng)路徑
交易的深度
從當(dāng)前這個(gè)交易到某個(gè)tip（未被驗(yàn)證的交易）的最長(zhǎng)路徑
交易的積分
當(dāng)前這筆交易的自身權(quán)重與所有它驗(yàn)證的那些交易的自身權(quán)重之和
例子
如上圖，一個(gè)小方框代表一筆交易，方框右下角較小的數(shù)字表示這筆交易的自身權(quán)重溶耘，方框中字體較大的數(shù)字代表這筆交易的累計(jì)權(quán)重。
交易F經(jīng)過(guò)交易A庐扫、B铅辞、C巷挥、E四個(gè)交易直接或者間接被驗(yàn)證。交易F的累計(jì)權(quán)重就是交易A高职、B、C埃元、E四個(gè)交易的各自自身權(quán)重之和崭孤，即 9=3+1+3+1+1。
一開(kāi)始的Tips是交易A和交易C。當(dāng)一個(gè)新的交易X被添加到網(wǎng)絡(luò)中还最，并對(duì)交易A和交易C進(jìn)行了驗(yàn)證之后，交易X就成為了網(wǎng)絡(luò)中唯一的Tip毡惜。同時(shí)拓轻，整個(gè)網(wǎng)絡(luò)中的其他所有交易的累計(jì)權(quán)重都增加3（即交易X的自身權(quán)重）。
交易G的高度為1经伙，深度為4（最長(zhǎng)路徑為：G-F-D-B-A）扶叉。而交易F的高度為2（最長(zhǎng)路徑為：創(chuàng)始交易-G-F）勿锅，深度為3（最長(zhǎng)路徑為：F-D-B-A）。
交易A直接或間接驗(yàn)證了交易B枣氧、D溢十、F、G达吞，因此交易A的積分=1+3+1+3+1=9张弛。同樣的，交易C直接或間接驗(yàn)證了D酪劫、E吞鸭、F、G覆糟，因此交易C的積分=1+1+1+3+1=7刻剥。
DAG相比于傳統(tǒng)區(qū)塊鏈的優(yōu)勢(shì)
1）數(shù)據(jù)結(jié)構(gòu)保證了較強(qiáng)的可擴(kuò)展性
? ? ? ? DAG中，每筆交易都能看作一個(gè)區(qū)塊滩字，每個(gè)區(qū)塊有多個(gè)指向造虏。拓展性強(qiáng)，無(wú)容量限制麦箍。隨著 參與者的增多漓藕，網(wǎng)絡(luò)也會(huì)趨向穩(wěn)定，區(qū)塊確認(rèn)時(shí)間也越來(lái)越快挟裂。
2）共識(shí)機(jī)制帶來(lái)的零手續(xù)費(fèi)
? ? ? ? 傳統(tǒng)的區(qū)塊鏈中撵术，交易者和礦工是分開(kāi)的，這樣就容易導(dǎo)致算力中心化和高昂的手續(xù)費(fèi)等問(wèn)題话瞧；而DAG中，交易者本身也是礦工寝姿，這樣網(wǎng)絡(luò)能完全去中心和交排，也無(wú)需支付手續(xù)費(fèi)。
參考資料：
1. http://iota.cn/iota是什么饵筑？（持續(xù)更新中）/
2. https://steemit.com/cn/@chiangqiqi/dag
3.?http://www.iotachina.com/iotadechangjianwentijieda.html
