DAG意思是有向無環圖，所謂有向無環圖是指任意一條邊有方向，且不存在環路的圖。如果有一個非有向無環圖，且A點出發向B經C可回到A，形成一個環。將從C到A的邊方向改為從A到C，則變成有向無環圖。有向無環圖的生成樹個數等於入度非零的節點的入度積。
基本介紹
- 中文名：有向無環圖
- 外文名：Directed Acyclic Graph
- 英文縮寫：DAG
- 特點：任意一條邊有方向，且不存在環路
有向無環圖DAG
算法中有時稱有向無環圖為DAG ( Directed Acyclic Graph)。所謂有向無環圖是指：任意一條邊有方向，且不存在環路的圖。
在數學與計算機科學中，如果一個有向圖從某個頂點出發，無法經過若干條邊回到該點，則這個圖是一個有向無環圖，或有向非循環圖（DAG圖，Directed Acyclic Graph）。有向非循環圖不含有有向循環，即它由有限個頂點（節點）和邊（弧）組成，每一條邊都從一個頂點指向另一個頂點。
DAG圖（源於維基百科）DAG是一個有向圖，它具有拓撲順序，頂點的序列使得每個邊在序列中都是由前到後定向的。
DAG可以模擬多種不同的信息，例如電子表格。當一個單元格中的公式使用另一個單元格的值時，每個單元格都有一個頂點和一條邊；當電子表格更改時，可以使用此DAG的拓撲順序更新所有單元格值。
同樣，可以使用DAG的拓撲順序來對makefile中的編譯操作進行排序。項目評估和評審技術使用DAG來模擬大型人類項目的里程碑和活動，並將這些項目安排在儘可能少的總時間內。電子電路設計中的組合邏輯塊以及數據流程式語言中的操作也會涉及到處理元件的非循環網路。DAG還可以表示事件集合及其相互影響，無論是在機率結構（如貝葉斯網路）中，還是作為歷史數據記錄（如家族樹），或分散式修訂控制系統的版本歷史記錄。DAG還可以用作序列數據的緊湊表示，例如字元串集合的有向非循環字圖表示，或二進制選擇序列的二進制決策圖表示。更抽象地說，DAG中的可達性關係形成了一個偏序，任何有限的偏序都可以用可達性來表示。
