有向無環圖（DAG）的溫故知新

當我們學習數據結構的時候，總是覺得很枯燥，而當我們解決實際問題的時候，又往往因爲對數據結構瞭解的匱乏而束手無策。從問題中來，到問題中去，在某一點上的深入思考並且不斷的實踐積累，或許是個笨辦法，但笨辦法總是比沒辦法好一些。本文是老碼農對 DAG 的隨手筆記，積累成文。

什麼是 DAG？

DAG，Directed Acyclic Graph 即「有向無環圖」。

從計算機的視角來看，DAG 是一個圖，圖與數組、隊列、鏈表等一樣，都是是一種數據結構。圖是由頂點和連接頂點的邊構成的數據結構，在計算機科學中，圖是最靈活的數據結構之一，很多問題都可以使用圖模型進行建模求解。例如，人與人之間的社交網絡、分析計算機網絡的拓撲結構已確定兩臺計算機是否可以通信、物流系統中找到兩個地點之間的最短路徑等等。

回顧一下圖的相關概念：

如果圖中的邊可以是有方向的，邊的方向性表明了兩個頂點直接的不同不關係。例如，地圖應用中必須存儲單行道的信息，避免給出錯誤的方向。如果圖中任意兩個頂點之間的邊都是有向邊，這個圖就是有向圖。如果有一個非有向無環圖，且 A 點出發向 B 經 C 可回到 A，形成一個環。將從 C 到 A 的邊方向改爲從 A 到 C，則變成有向無環圖，即 DAG。

按照數學上的定義，DAG 是一個沒有有向循環的、有限的有向圖。具體來說，它由有限個頂點和有向邊組成，每條有向邊都從一個頂點指向另一個頂點；從任意一個頂點出發都不能通過這些有向邊回到原來的頂點。也就是說，它由 頂點 Vertex 和 邊 Edge (也稱爲弧) 組成，每條邊都從一個頂點指向另一個頂點，沿着這些頂點的方向 不會形成一個閉合的環 。DAG 與代數拓撲學中的偏序集（Partially Ordered Set，Poset）有緊密聯繫。偏序關係相同的任意兩個圖會有相同的拓撲排序集。事實上，任何一個 DAG 都唯一對應一個 Poset, 而所有的 Poset 都是 DAG，所以它們在本質上是一種事物。

DAG 具有一些很好性質，比如很多動態規劃的問題都可以轉化成 DAG 中的最長路徑、最短路徑或者路徑計數的問題。

DAG 的特性

DAG 具有空間結構和時間序列的混合特性，與數據結構中的樹密切相關，其拓撲排序和最短路徑的計算，都有着獨到的特點。

DAG 與樹的關係

DAG 是樹的泛化, 也是 ploy tree 的泛化。tree 是層次化，按照類別或者特性可以細分到原子單元，樹其實就是一種無環連通圖。DAG 從源開始細分，但是中間可以有合，有彙總。D 就是可以合的點。

因爲有向圖中一個點經過兩種路線到達另一個點未必形成環，因此有向無環圖未必能轉化成樹，但任何有向樹均爲有向無環圖。

DAG 的拓撲排序

拓撲排序是一個可以把所有的頂點排序的算法，它排序的依據是深度優先搜索算法的完成時間。可以根據拓撲排序來計算有向無環圖（的單源最短路徑），因爲拓撲排序正好是建立在無環的基礎上，在這個圖中沒有負權重邊以及迴路邊。

拓撲排序是將圖中所有頂點排成一個線性序列，使得圖中任意一對頂點 u 和 v，若邊 (u,v)∈E(G)，則 u 在線性序列中出現在 v 之前。通常，這樣的線性序列稱爲滿足拓撲次序的序列，簡稱拓撲序列。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之爲拓撲排序。

對於一個 DAG，可以這樣確定一個圖中頂點的順序：對於所有的 u、v，若存在有向路徑 u-->v，則在最後的頂點排序中 u 就位於 v 之前。這樣確定的順序就是一個 DAG 的拓撲排序。拓撲排序的特點如下：（1）所有可以到達頂點 v 的頂點 u 都位於頂點 v 之前；（2）所有從頂點 v 可以到達的頂點 u 都位於頂點 v 之後。

另外，只有有向無環圖才存在拓撲排序，一個圖的拓撲順序不唯一。

實現拓撲排序主要有兩種方法：入度表和 DFS。在 DFS 實現拓撲排序時，用棧來保存拓撲排序的頂點序列；並且保證在某頂點入棧前，其所有鄰接點已入棧。下面列出的是用 C 語言實現的入度表拓撲排序示例代碼：

#define MAX_NODE 1000
#define MAX_EDGE_NUM 100000
struct Edge{
    int to;
    int w;
    int next;
};
Edge gEdges[MAX_EDGE_NUM];
int gHead[MAX_NODE];
bool gVisited[MAX_NODE];
int gInDegree[MAX_NODE];
int gEdgeCount;
void InsertEdge(int u,int v,int w){
    int e = gEdgeCount++;
    gEdges[e].to = v;
    gEdges[e].w = w;
    gEdges[e].next = gHead[u];
    gHead[u] = e;
    gInDegree[v] ++;   //入度加1
}
void TopoSort(int n/*節點數目*/){
    queue<int> zero_indegree_queue;
    for (int i = 0; i < n; i++){
    　 if (gInDegree[i] == 0)
              zero_indegree_queue.push(i);
    }
    memset(gVisited,false,sizeof(gVisited));
    while (!zero_indegree_queue.empty()){
        int u = zero_indegree_queue.front();
        zero_indegree_queue.pop();
        gVisited[u] =true;
        //輸出u
        for (int e = gHead[u]; e != -1; e = gEdges[e].next){
            int v = gEdges[e].to;
            gInDegree[v] --;
            if (gInDegree[v] == 0){
                zero_indegree_queue.push(v);
            }
        }
    }
    for (int i = 0; i < n; i++){
        if (!gVisited[i]){
            //環！無法形成拓撲序
        }
    }
}

DAG 的單源最短路徑

圖中節點的單源最短路徑可以使用 Dijkstra,BellmanFord, SPFA 算法，而對於有向無環圖 DAG 來說，可以通過簡單的動態規劃來進行求解。DAG 的獨特之處是所有節點可以線性化（拓撲序列），使得所有邊保持從左到右的方向。

給定一個 DAG 和一個源點，可以得到該源點到其他所有的頂點的最短路徑。如果是無負權，可以用 djistra 算法完成。但如果存在負權，則不行。同時，djistra 算法效率並不高，既然是 DAG，則可以利用拓撲排序的結果求出給定源點的最短路徑，其時間複雜度是線性時間複雜度 O（V+E）。

DAG 的單源最短路徑算法原理如下：

  1. 初始化 dist[] = {INF, INF, ….} ，dist[s] = 0 是單源頂點 

  2. 創建所有定點的拓撲排序

  3. 對拓撲排序中的每個頂點 u 做如下處理，即處理 u 的每個相鄰頂點：if (dist[v] > dist[u] + weight(u, v)) dist[v] = dist[u] + weight(u, v) 

具體地， 用 Python 實現的 DAG 最短路徑算法代碼示例如下：

# Python program to find single source shortest paths
# for Directed Acyclic Graphs Complexity :OV(V+E)
from collections import defaultdict
 
# Graph is represented using adjacency list. Every
# node of adjacency list contains vertex number of
# the vertex to which edge connects. It also contains
# weight of the edge
class Graph:
    def __init__(self,vertices):
 
        self.V = vertices # No. of vertices
 
        # dictionary containing adjacency List
        self.graph = defaultdict(list)
 
    # function to add an edge to graph
    def addEdge(self,u,v,w):
        self.graph[u].append((v,w))
    # A recursive function used by shortestPath
    def topologicalSortUtil(self,v,visited,stack):
 
        # Mark the current node as visited.
        visited[v] = True
 
        # Recur for all the vertices adjacent to this vertex
        if v in self.graph.keys():
            for node,weight in self.graph[v]:
                if visited[node] == False:
                    self.topologicalSortUtil(node,visited,stack)
 
        # Push current vertex to stack which stores topological sort
        stack.append(v)
     ''' The function to find shortest paths from given vertex.
        It uses recursive topologicalSortUtil() to get topological
        sorting of given graph.'''
    def shortestPath(self, s):
 
        # Mark all the vertices as not visited
        visited = [False]*self.V
        stack =[]
 
        # Call the recursive helper function to store Topological
        # Sort starting from source vertice
        for i in range(self.V):
            if visited[i] == False:
                self.topologicalSortUtil(s,visited,stack)
 
        # Initialize distances to all vertices as infinite and
        # distance to source as 0
        dist = [float("Inf")] * (self.V)
        dist[s] = 0
 
        # Process vertices in topological order
        while stack:
 
            # Get the next vertex from topological order
            i = stack.pop()
 
            # Update distances of all adjacent vertices
            for node,weight in self.graph[i]:
                if dist[node] > dist[i] + weight:
                    dist[node] = dist[i] + weight
 
            # Print the calculated shortest distances
            for i in range(self.V):
                 print ("%d" %dist[i]) if dist[i] != float("Inf") else  "Inf" ,
     g = Graph(6)
g.addEdge(0, 1, 5)
g.addEdge(0, 2, 3)
g.addEdge(1, 3, 6)
g.addEdge(1, 2, 2)
g.addEdge(2, 4, 4)
g.addEdge(2, 5, 2)
g.addEdge(2, 3, 7)
g.addEdge(3, 4, -1)
g.addEdge(4, 5, -2)
 
# source = 1
s = 1
 
print ("Following are shortest distances from source %d " % s)
g.shortestPath(s)
 
# This code is contributed by Neelam Yadav

DAG 的應用

鑑於 DAG 的一般性，具有廣泛的應用場景。

DAG 的存儲結構用例

作爲數據結構，DAG 在數據存儲方面非常著名的使用場景就是 Git。Git 採用了 Merkle Tree+ DAG 作爲一個組合的數據結構 Merkle DAG，來實現了分佈式的的版本控制。

IPFS 參考了 Git 的實現思想，同樣使用了 Merkle DAG 作爲核心的數據結構，即後來稱爲 IPLD， 在 IPFS 生態系統的 “蜂腰” 模型中處於腰的位置，如下圖所示： 

Merkle Tree 通常也被稱作 Hash Tree，顧名思義，就是存儲 hash 值的一棵樹。在 Merkle Tree 的基礎上，Merkle DAG 是一個有向無環圖，可以簡單的理解成一棵樹，且沒有 Merkle Tree 那樣嚴格的限制（例如平衡樹），其特點是：

Merkle DAG 保留了 Merkle Tree 的精華部分，即任何一個下層節點改動，都將導致上層節點的哈希值變動，最終的根節點的哈希值也變動。在 IPFS 網絡中，存儲文件時，首先會將文件切片，切割成 256KB 大小的文件。之後循環調用（MerkleDAG.Add）方法構建文件 MerkleDAG。文件 hash 值創建流程如下： 

  1. 將切片之後的文件進行 sha-256 運算 

  2. 將運算結果選取 0~31 位 

  3. 將選取結果根據 base58 編碼，運算結果前追加 Qm 即爲最後結果作爲文件的 46 位 hash 值。

在 IPFS 中，使用 DAGService 維護 MerkleDAG，爲 MerkleDAG 提供刪除和增加的權限。其中的 Merkle DAG 爲多叉樹結構，最多爲 174 叉樹。

通過 Merkle DAG， IPFS 能夠輕鬆確保和驗證 P2P 格式的計算機之間共享數據的完整性，這使得它們對系統非常有用。

DAG 的因果關係用例

以探討影響因素或者控制偏倚爲目的迴歸模型，要求自變量和因變量往往存在着因果關係，所以自變量篩選首先需要考慮自變量能否納入到模型，嚴格挑選自變量進入模型。

DAG 可以說是迴歸分析的靈魂所在，是最高指導方針。基於 DAG 構建因果關係網絡，從而找到合適進入模型的自變量。箭頭髮出對象爲因，箭頭指向爲果。所有變量因果關係通過方向線形成的單向網絡，即 DAG。

例如，貝葉斯網絡是表示多個概率事件的關聯網絡。頂點表示事件，後續事件的發生可能性則可以通過其在有向無環圖的前驅節點的發生概率計算出來。

動態規劃的 DAG 實現

什麼是動態規劃呢？問題可以分解成若干相互聯繫的階段，在每一個階段都要做出決策，全部過程的決策是一個決策序列。要使整個活動的總體效果達到最優的問題，稱爲多階段決策問題。動態規劃就是解決多階段決策最優化問題的一種思想方法。

將所給問題的過程，按時間或空間特徵分解成若干相互聯繫的階段，以便按次序去求每階段的解。各階段開始時的客觀條件叫做狀態。當各段的狀態取定以後，就可以做出不同的決定，從而確定下一階段的狀態，這種決定稱爲決策。具體地，動態規劃的遞推需要一個線性或者樹形的順序，對於 DAG，可以將節點按照拓撲順序來進行線性化。具體地，對於當前的節點 v，在拓撲序列中向前查找，可能找到一些可以到達該頂點的其他節點，然後利用 dist[v] = min{dist[u] + w[u][v] | u 可以到達v}來進行動態規劃的遞推。

基於 DAG 調度用例

在有相互依賴的調度系統中，DAG 有着非常典型的應用。這裏以 Spark 爲例進行說明。

在 Spark 中的每一個操作生成一個 RDD，RDD 之間形成一條邊，最後這些 RDD 和他們之間的邊組成一個有向無環圖，這個就是 DAG。

Spark 中的 RDD 依賴關係分爲兩種：窄依賴 (Narrow Dependencies) 與寬依賴 (Wide Dependencies，源碼中稱爲 Shuffle Dependencies) 會根據寬依賴窄依賴來劃分具體的 Stage，而依賴有 2 個作用：

原始的 RDD 通過一系列的轉換就形成了 DAG，有了可計算的 DAG，Spark 內核下一步的任務就是根據 DAG 圖將計算劃分成任務集，也就是 Stage，這樣可以將任務提交到計算節點進行真正的計算。Spark 計算的中間結果默認是保存在內存中的，Spark 在劃分 Stage 的時候會充分考慮在分佈式計算中可流水線計算的部分來提高計算的效率，而在這個過程中 Spark 根據 RDD 之間依賴關係的不同將 DAG 劃分成不同的 Stage。對於窄依賴，partition 的轉換處理在一個 Stage 中完成計算。對於寬依賴，由於有 Shuffle 的存在，只能在 parent RDD 處理完成後，才能開始接下來的計算，因此寬依賴是劃分 Stage 的依據。

Spark 執行時的處理流程如下：

1）用戶代碼定義 RDD 的有向無環圖

RDD 上的操作會創建新的 RDD，並引用它們的父節點，這樣就創建了一個圖。

2）行動操作把有向無環圖強制轉譯爲執行計劃

當調用 RDD 的一個行動操作時，這個 RDD 就必須被計算出來。這也要求計算出該 RDD 的父節點。Spark 調度器提交一個作業來計算出所有必要的 RDD。這個作業會包含一個或多個步驟，每個步驟其實也就是一波並行執行的計算任務。一個步驟對應有向五環圖中的一個或多個 RDD，一個步驟對應多個 RDD 是因爲發生了流水線執行。

3）任務於集羣中調度並執行 

步驟是按順序處理的，任務則獨立的啓動來計算出 RDD 的一部分。一旦作業的最後一個步驟結束，一個行動操作也就執行完了。

DAG 的區塊鏈用例

最早在區塊鏈中引入 DAG 概念作爲共識算法是在 2013 年，bitcointalik.org 由 ID 爲 avivz78 的以色列希伯來大學學者提出，也就是 GHOST 協議，作爲比特幣的交易處理能力擴容解決方案；Vitalik 在以太坊紫皮書描述的 POS 共識協議 Casper，也是基於 GHOST POW 協議的 POS 變種。

後來，有人提出用 DAG 的拓撲結構來存儲區塊，解決區塊鏈的效率問題。區塊鏈只有一條單鏈，打包出塊無法併發執行。如果改變區塊的鏈式存儲結構，變成 DAG 的網狀拓撲就可以實現併發寫入。在區塊打包時間不變的情況下，網絡中可以並行打包 N 個區塊，網絡中的交易效率就提升了 N 倍。

那個時候，DAG 跟區塊鏈的結合依舊停留在類似側鏈的解決思路，交易打包可以並行在不同的分支鏈條進行，達到提升性能的目的。此時，DAG 還是區塊的概念。

2015 年 9 月，Sergio Demian Lerner 發表了 《DagCoin: a cryptocurrency without blocks》一文，提出了 DAG-Chain 的概念，首次把 DAG 網絡從區塊打包這樣粗粒度提升到了基於交易層面。DagCoin 的思路，讓每一筆交易都直接參與維護全網的交易順序。交易發起後，直接廣播全網，這樣省去了打包交易出塊的時間。也就是說，交易發起後直接廣播網絡確認，理論上效率得到了質的飛躍。

進一步，DAG 演變成了完全拋棄區塊鏈的一種解決方案。2016 年 7 月，基於 IOTA 橫空出世，隨後 ByteBall 也登場了，IOTA 和 Byteball 是頭一次 DAG 網絡的真正技術實現，此時，號稱無塊之鏈、獨樹一幟的 DAG 鏈家族雛形基本形成。

從某種程度上說，DAG 可能是面向未來的新一代區塊鏈，從單鏈進化到樹狀和網狀、從區塊粒度細化到交易粒度、從單點躍遷到併發寫入，這是區塊鏈從容量到速度的一次革新。

一句話小結

有向無環圖有許多科學的和計算的應用，從生物學到社會學再到我們所熟悉的計算機領域，而且，DAG 的原理並不複雜，關鍵在於把目標問題抽象爲 DAG，進而使用 DAG 的相關特性來解決問題。

【參考資料與關聯閱讀】 

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/13qrmJFyIP9w2vicx6NBaA

猜你喜歡