dag圖演算法

A. 對於一個復雜的有向無環網路，怎麼尋找它的一個子圖，其中子圖內的箭頭只在子圖內，也就是個閉集這

說明不清晰。什麼叫子圖內的箭頭只在子圖內？我猜你想說，子圖中的任意節點只能指向該子圖內某個節點，不能指向子圖外部的節點。
方法是：找到該DAG圖的所有葉子節點（出度為0的節點）。如果該子圖只包括一個葉子，則該子圖是以該葉子節點為根的反向DAG圖（即從該節點出發，逆著邊的方向，得到反向DAG圖。這顯然不唯一，非常多）；如果包括多個葉子（比如n個葉子），則該子圖是前面n個反向DAG圖的並。
總之，一個很簡單的DAG圖就有很多這種子圖，非常多。前面的演算法中含有冗餘的計算，可以進一步改善。

B. 什麼是DAG區塊鏈技術

DAG全稱是「有向無環圖」，沒有區塊概念，不是把所有數據打包成區塊，再用區塊鏈接區塊，而是每個用戶都可以提交一個數據單元，這個數據單元里可以有很多東西，比如交易、消息等等。數據單元間通過引用關系鏈接起來，從而形成具有半序關系的DAG（有向無環圖）。DAG的特點是把數據單元的寫入操作非同步化，大量的錢包客戶端可以自主非同步地把交易數據寫入DAG，從而可以支持極大的並發量和極高的速度。同時，使用DAG技術的TrustNote還支持聲明式智能合約，聲明式的智能合約要表達的意思是可以直接按照用戶想要的結果去寫、去描述，以很簡單的語言，讓大家都能看懂的語言去描述他要乾的事情。

截止到2017年年底，「高流量應用」越來越多，除了主流電商平台外，還有直播平台、P2P理財、今日頭條、陌陌等嶄露頭角，如果「高流量應用」與DAG區塊鏈技術結合，將會給行業帶來哪些變革呢？除區塊鏈自身的特點去中心化、分布式賬本、不可篡改之外，DAG區塊鏈技術不但可以支持高並發，結合雙層共識機制，使用工作量證明共識演算法，還能夠防止「雙花」問題。

那麼，DAG如何支持高並發的呢？第一，數據不像比特幣和以太坊一樣強同步，而是弱同步，允許節點在同一時刻數據不一樣，數據可以有一些微小的差別。第二，可以通過數據單元之間的引用來完成交易的確認，就是後面發生的單元去引用前面的單元，這樣不需要我們把數據傳給礦工，整個過程都是由自己去完成的，這個過程很快。DAG是解決高並發比較優美的方法，比起之前的閃電網路，還有其他一些方面，DAG有其先天優勢。

再來看看DAG是如何防止「雙花」？在有向圖里如果能選出一個MainChain，這個時候會發現所有圖裡面的節點都可以用一種方法來給它做排序，把這個序號連接起來在一排，這張圖將會變成跟區塊鏈一樣的序列結構，就是排完序的節點，而且每個節點是一個交易，而不是一個區塊。所以，確定了主鏈，通過主鏈，可以形成全序。最後達到的結局就是在某一個邏輯狀態里，交易還是被排序了，這是DAG最關鍵核心的部分。

「高流量應用」是隨著節點數和交易數的增加平滑擴展，當這個節點數超過1億或交易數超過並發100萬時，DAG的特性剛好是交易越多越快，節點越多越快。

C. 基本塊的dag圖怎麼畫

基本塊構造步驟:

(1): 由規則 (1) 中的 1 可知語句 (1) 是一個入口語句

(2): 由規則 (1) 中的 2 可知, 語句 (3) 和 (8) 均是人口語句

(3): 由規則 (1) 中的 3 可知, 語句 (5) 是二個人口語句, 可以用 "+" 在人口語句的左側作標記.

(4): 由規則 (2) 可以劃分該程序為四個基本塊, 它們分別是:

語句 (1),(2) 組成的基本塊 B1

語句 (3),(4) 組成的基本塊 B2

語句 (5),(6) 和 (7) 組成的基本塊 B3

語句 (8) .(9) 組成的基本塊 B4

程序中在代碼段左側對各個基本塊進行了標記.

(三)程序控制流程流圖

定義: 以基本塊為結點, 控製程序流向作為有向邊, 畫出的有向圖稱為流圖.

特點:

具有唯一首結點的有向圖

從首結點開始到流圖中任何結點都有通路

如果一個結點的基本塊的入口語句是程序的第一條語句, 則稱此結點為首結點

程序控制流程流圖的表示

一個控制流程圖可表示成一個三元組:

G=(N,E,n0 )

N: 所有結點 (基本塊) 集;

E: 所有有向邊集;

n0 : 首結點.

有向邊:

當下述條件有一個成立時, 從結點 i 有一有向邊引向結點 j:

1 基本塊 j 在程序的位置緊跟在 i 後, 且 i

D. 什麼是DAG

參考 Explaining Directed Acylic Graph (DAG), The Real Blockchain 3.0

Bitcoin視為blockchain 1.0, Ethereum視為2.0, 那麼3.0是什麼? DAG可能會是.

DAG, 即Direct Acyclic Graph, 有向無環圖. 它的特點是節點有先後次序, 可以有分叉, 但還不會有環. DAG常用語數據處理, 事務規劃, 最優路徑查找, 數據壓縮

bitcoin之所以效率低是因為它的POW機制. 整個網路只有一個主鏈, 其上的新塊只能有一個, 無法同時創建多個新塊. 10分鍾左右以內的所有交易記錄都被記錄到一個塊中. Ethereum也是類似, 大概15-20秒產生一個新塊.

NXT 是第一個想到用DAG替代blockchain單鏈表結構的組織.

有了DAG, 就可以同一時間創建多個塊.

使用DAG的想法來自於側鏈(side-chain). 不同類型的交易在不同的鏈上同時進行.

IoT Chain (ITC), IOTA , 和 Byteball 是沒有block概念的項目.

如果每個block只有一個transaction, 那這個transaction就不用等待被打包, 跳過計算hash的過程(即挖礦), 直接上鏈了.

Bitcoin使用UTXO(Unspent Transaction output)模型.

DAG網路中, 降低網路寬度是比較重要的一個課題.

由於只有transaction, 沒有打包的過程, DAG比基於PoW或PoS的區塊鏈更快.

DAG網路里, 沒有礦工. 交易的驗證直接在交易時進行. 對於用戶來說這意味著交易可以瞬間完成.

DAG可以有效降低交易費.

IoT Chain (ITC) 所基於的DAG的TPS達到10,000.

E. 如何判斷一個圖是否為有向無環圖（DAG）

判斷圖是否為有向無環圖的基本思想為：從任意點出發，都不會再回到該點。
Description：
Input:鄰接矩陣
color:用來記錄節點被訪問的情況。『0』代表未被訪問過，『1代表正在訪問』，『-1』代表該點的後裔節點都已經被訪問過。在一次搜索中，若某點的狀態為1，則該點之前被訪問過，存在環。若某點的狀態為『-1』，則該點的後裔點均被訪問過，跳過該次搜索。若某點的狀態為『0』，則該點之前沒有被訪問過，DFS該點。

本文分別用一個有向無圈圖和一個有向有圈圖做測試：

F. dag圖的介紹

DAG數據結構跟蹤基本塊中值和變數的計算和賦值 ；塊中使用的來自別處的值表示為葉子結點 ；值上的操作表示為內部結點 ；新值的賦值表示為將目標變數或臨時變數的名字附加到表示賦值的結點上。

G. 有誰知道能解釋一下有向無環圖(DAG)么怎麼用程序做出來，及怎麼應用到經濟學實證上

我們說區塊鏈目前還不成熟，有各種各樣的問題，比如說處理速度慢、手續費高昂、存在安全隱患等等，這些都是用戶最直觀的體驗，體驗不是太好。區塊鏈還有一個問題，那就是高並發問題。
高並發問題是怎麼回事呢，我們簡單說一下。高並發是計算機領域的問題，簡單來講，高並發問題就是系統無法順利同時運行多個任務。
很多任務同時運行，一大堆用戶涌進來，系統承受不住這么多的任務，會出現高並發問題，你的系統就卡住了，就好比春運時候，12306系統總是卡住，有可能就是高並發問題造成的。
傳統互聯網尚且存在高並發問題，區塊鏈網路自然也存在這個問題，畢竟區塊鏈的成熟程度比起傳統互聯網，還有很大的差距。但是，如果沒有安全、可靠和高效的公鏈，整個區塊鏈產業的發展都將受到嚴重製約，應用落地也是空談。
在這種背景下，DAG 技術就被提出來了，DAG 的全稱是「Directed Acyclic Graph」，中文翻譯為「有向無環圖」。
DAG有向無環圖是怎麼回事呢，它到底能起到什麼作用呢？我們下面解釋一下。
一、DAG：一個新型的數據結構
DAG，中文名字叫「有向無環圖」，從字面意思看，「有向"就是說它是有方向的，
「無環」就是說它是沒有環路的、不能形成閉環的。所以，DAG其實是一種新型的數據結構，這個數據結構是有方向的，同時又是不能形成閉環的。
傳統區塊來講，我們總是以「區塊」為單位，一個區塊里往往包含了多筆交易信息。而在DAG中，沒有區塊的概念，而是以「單元」為單位，每個單元記錄的是單個用戶的交易，組成的單元不是區塊，而是一筆筆的交易，這樣一來，可以省去打包出塊的時間。
簡單來說，區塊鏈和DAG有向無環圖最大的區別就是：區塊鏈是一個接一個的區塊來存儲和驗證交易的分布式賬本，而DAG則是把每筆交易都看成一個區塊，每一筆交易都可以鏈接到多個先前的交易來進行驗證。
二、DAG 的工作原理
傳統區塊鏈上，就拿比特幣來講，它是單鏈式的結構，區塊與區塊之間按照時間戳的先後順序排列開來（如圖一），數據記錄在一條主鏈上。用不太恰當的比喻來講，這個
「單鏈式」結構是一條一字排列的鏈。
區塊鏈只有一條單鏈，打包出塊就無法並發執行。新的區塊會加入到原先的最長鏈之上，所有節點都以最長鏈為准，繼續按照時間戳的順序無限蔓延下去。而對於DAG來講，每個新加入的單元，不僅只加入到最長鏈的一個單元，還要加入到之前所有的單元（如圖二）。
舉個例子：假設我發布了一個新的交易，此時DAG結構已經有2個有效的交易單元，那麼我的交易單元會主動同時鏈接到前面的2個之中，去驗證並確認，直到鏈接到創世單元，而且，上一個單元的哈希會包含到自己的單元裡面。
換句話說，你要想進行一筆交易，就必須要驗證前面的交易，具體驗證幾個交易，根據不同的規則來進行。這種驗證手段，使得DAG可以非同步並發的寫入很多交易，並最終構成一種拓撲的樹狀結構，極大地提高擴展性。
依據DAG有向無環圖，每一筆交易都直接參與了維護全網。當交易發起後，直接廣播全網，跳過礦工打包區塊階段，這樣就省去了打包交易出塊的時間，提升了區塊鏈處理交易的效率。
隨著時間遞增，所有交易的區塊鏈相互連接，形成圖狀結構，如果要更改數據，那就不僅僅是幾個區塊的問題了，而是整個區塊圖的數據更改。DAG這個模式相比來說，要進行的復雜度更高，更難以被更改。
總結一下，DAG作為一種新型的去中心化數據結構，它屬於廣義區塊鏈的一種，具備去中心化的屬性，但是二者的不同之處在於：
區塊鏈組成單元是Block（區塊），DAG組成單元是TX（交易）。
區塊鏈是單線程，DAG是多線程。
區塊鏈所有交易記錄記在同一個區塊中，DAG每筆交易單獨記錄在每筆交易中。
區塊鏈需要礦工，DAG不需要礦工。
三、 DAG 的代表：IOTA
DAG當前的代表項目，最知名的無疑就是 IOTA。可以說，正是因為IOTA這個幣種在 2017年下半年沖進市值排行第四位，才使人們真正認識到了它的底層技術：DAG有向無環圖。
IOTA在DAG有向無環圖的基礎上提出了「纏結」概念，在IOTA裡面，沒有區塊的概念，共識的最小單位是交易。每一個交易都會引用過去的兩條交易記錄哈希，這樣前一交易會證明過去兩條交易的合法性，間接證明之前所有交易的合法性。這樣一來， 就不再需要傳統區塊鏈中的礦工這樣少量節點來驗證交易、打包區塊，從而提升效率，節省交易費用。
四、 DAG 的現狀
盡管理論上來講，DAG有向無環圖能夠彌補傳統區塊鏈的一些弊端，但是目前並不成熟，應用到數字貨幣領域的時間也比較短，還比較年輕 。
它沒有像比特幣那般經過長達10年的時間來驗證整個系統的安全性，也沒有像以太坊那般實現了廣泛的應用場景。不過，現在有些聲音提出要採用「傳統區塊鏈+DAG」的數據結構，但是還沒有非常突出的案例，這里就不多說了。
總結一下，本節我們介紹了區塊鏈的衍生技術：DAG有向無環圖，這是一種全新的數據結構，可以對區塊鏈處理交易的效率、並發力達到顯著的提升。

H. 『學概念找員外』有向無環圖DAG的用途

有向無環圖（DAG, Directed Acyclic Graph） ：是一個無迴路的有向圖。如果有一個圖，從A點出發到B點，然後經過C點，最後可以順著方向回到A，形成一個閉環，那麼這個圖就不是非向無環圖。如果將從C到A的邊方向改為從A到C，則變成有向無環圖。如圖1 和 圖2。

看到這兩幅圖，應該可以明白了，當然這個圖是很簡單的，只有三個點，事實上可能是由百萬千萬或者更多個點組成的圖。有向無環圖就是從一個圖中的任何一點出發，不管走過多少個分叉路口，都沒有回到原來這個點的可能性。

拓撲排序 ：就是一個有向無環圖的所有定點的線性序列。且這個序列必須滿足這兩個條件：

這個東西，是比較難理解，再上圖說話吧。比如在這個有向無環圖中，它用拓撲排序，該怎麼進行呢？

最後，一個完整的拓撲排序就完成了，結果為：1、2、4、3、5。

大家都知道，在比特幣系統中，固定約十分鍾出一個塊，而且一旦打包成功一個區塊，這個區塊的信息還必須同步到其他的所有區塊上面去，這是極其耗費資源和時間的。同時一個塊裡面大概能容納3000筆交易，也就意味著10分鍾才能交易成功3000筆。這個交易速度實在是滿足不了用戶的需求，所以為了解決比特幣這個問題，出現了各種分叉幣，也可謂是把比特幣搞的亂七八糟了。後來以太坊問世後，基於比特幣的基礎上，交易速度提高了不少，每秒交易可達到20筆左右，但是任然有多次的以太坊擁堵事件，證明這個交易速度還遠遠不夠。

在比特幣系統中，如果可以改變51%的節點的記錄數據，那麼就實現了惡意攻擊。然而現在比特幣的大部分算力掌握在少數幾個較大的礦廠手裡，雖然大家都有共識，不會發起惡意攻擊，但是不代表不會有意外事件發生。

隨著計算機硬體的不斷迭代升級，量子計算機的問世，那麼比特幣的加密演算法還會有用嗎？會不會被破解掉？雖然比特幣的哈希演算法可以實時調整難度，但是到底能承受多大的考驗，員外是說不清的。

比特幣用於大額的跨境轉賬或者交易等用途，還是挺實用的，但是誰會去用比特幣購買小件商品？顯然是不可能的，交易手續費就會讓你心疼半天，然後還得再等半天的確認時間。

在區塊鏈的應用上使用了DAG圖之後，可以使得出塊速度變快，因為DAG圖中的每個頂點都是一個在某一時間點打包完成的區塊。與傳統的公鏈一次性只能產出一個區塊來比，DAG的不同節點都可以自己來生成區塊，然後這個區塊只要選擇好自己的下一個或者多個區塊作為自己的子區塊就好了。僅僅是在這一點上，出塊速度就會高出比特幣多個量級，交易速度簡直可以快的飛起。

基於DAG的數據結構來說的話，對於裡面的每個節點來說，因為與之相連的節點很少，而且是有方向性的，只能往前不能後退，所以都不需要再等大量的其他節點達成共識後，再同時確認下一筆交易了，避免了因網路延遲和數據同步造成的大量時間浪費。所以，使用DAG記賬的節點的延展性可得到大幅度提升。

從上面這張圖中，可以看到DAG的每一個節點都可以向下連接任意多個新的節點，這個有什麼用呢？如果在這一個區塊內部交易數據或者與之相連的下一步的交易數據也是過多的話，那麼就可以分成足夠多個區塊來共同分擔區塊壓力，從而可以提高交易的吞吐量。相比於比特幣這樣的系統每次只能打包一個區塊來說，簡直是完勝。

沒有一個東西是完美的，有優勢就有缺點，所以DAG的缺點目前在安全問題上面，主要是雙花和影子鏈攻擊。這個問題員外目前還沒有找到足夠好的答案，只能後續再說了。

本文參加優享優質經驗徵集計劃，經驗即價值，優享為成長買單
全球首個去中心化經驗價值共享平台「優享」開啟今夏最強空投!注冊即送UX，最高5000UX，更多價值，等你發現！注冊鏈接