文章內容目錄
1. 有向無環圖（Directed Acyclic Graph，DAG）是一個有向圖，從任意頂點出發都無法經過邊回到該點。
2. 非環圖中從一個頂點到另一個頂點可能有多條路徑，因此它不一定能轉換成樹，但任何有向樹都是有向無環圖。
3. 無環圖由頂點和它們之間的邊構成，每個邊都有從一個頂點指到另一個頂點的方向。
4. 有向無環圖中的路徑是一系列邊，其中每個邊的終點都是下一個邊的起點，如果一條路徑的起點和終點相同，則稱之為環。
5. 如果存在一條從頂點a到頂點b的路徑，則b被稱為從a可達。每個頂點自能相達（通過一條無邊的路徑）。
6. 可達性可以使用頂點的偏序關係≤表示。在偏序關係中，如果a到b有一條路徑，則a ≤ b。這也表示b從a可達。
7. 不同的無環圖可能具有相同的可達關係和偏序關係。例如，有邊a → b和b → c的無環圖，以及有邊a → b、b → c和a → c的無環圖具有相同的偏序關係a ≤ b ≤ c。
8. 對於無環圖G，它的遞移閉包是一個圖，在保持其可達性的情況下，邊數最多。
9. 遞移規約是無環圖G的子圖，具有與其具有相同可達性的邊最少。
10. 遞移閉包和遞移規約是無環圖專有概念，而有環有向圖可能有多個與原圖具有相同可達性的最簡子圖。
11. 對於無環圖G和表達其可達性的偏序關係≤，它的遞移規約可以看作是包含G的覆蓋關係中的每一條邊的G的子圖。
12. 無環圖的拓撲排序是所有邊的起點都在其終點之前出現的排序。
13. 拓撲排序可以定義無環圖：當且僅當一個有向圖有拓撲排序時，它是一個無環圖。
14. 無環圖的拓撲排序一般不是唯一的，只有在存在一條路徑包含所有頂點的情況下，拓撲排序才與它們在這條路徑中出現的順序相同。
15. 無環圖的拓撲排序族等同於其可達性的線性拓展族。
16. 在1973年，羅賓遜研究了無環圖的圖計數問題。
17. 標號頂點在拓撲排序中出現的順序不受限制，則有n個頂點的標號無環圖的數量如下：
| Cn | = | Cn-1 | + | Cn-2 | + …… + | C0 |
其中n = 0, 1, 2, 3, …這個數列的遞歸關係式是：
| Cn | = | Cn-1 | + | Cn-2 |
18. 埃裏克·韋斯坦因推測，n個頂點的標號無環圖的數量與其中所有特徵值都為正實數的n*n邏輯矩陣的數量相同。
19. 將自由樹的邊定向得到的圖稱為多重樹。多重樹是無環圖。對有根樹，將其邊指定為從根指出的方向也可得到無環圖，即樹狀圖。
20. 強明確樹是一個每兩個頂點最多通過一條路徑連接的無環圖。等價的説法是：它是滿足以下性質的有向無環圖：對於圖中每個頂點v，從v可達的頂點組成一棵樹。
21. 可以使用線性時間複雜度的卡恩演算法來找到無環圖的拓撲排序。
22. 簡單來説，設立一個存放結果的列表L，將入度為零的節點放入L中，因為它們沒有父節點。將與這些節點相連的邊從圖中移除，再尋找圖中入度為零的節點。對於新找到的節點，它們的父節點已經在L中了，所以也可以從末端插入L。重複上述操作，直到找不到入度為零的節點。
23. 另一個構造拓撲排序的演算法是將深度優先搜尋的後序遍歷結果反轉。
24. 檢查一個有向圖是否為無環圖也可以在線性時間內完成。一種方法是先找到一個拓撲排序，然後測試這個排序是否能符合圖中每條邊所連頂點在排序中應該出現的順序。
25. 任意無向圖都可以轉換為無環圖。構造方法是選定一個頂點的全序關係，並將無向圖中所有邊從全序關係中較前的頂點指向較後的頂點。
26. 任意有環有向圖都可以轉換為無環圖。移除反饋節點集或反饋邊集即可，即對於圖中每個環，至少包括環中一個頂點或邊的集合。
27. 無環圖的遞移閉包可以使用廣度優先搜尋或深度優先搜尋對每個節點測試可達性來構建。
28. 不論哪種遞移閉包演算法，那些被一條長度至少為2的路徑所連接的頂點對，都可以和只有一條長度為1的路徑所連接的頂點對區分開。
29. 遞移約簡包含後者，因此它可以在和遞移閉包相同的漸進時間複雜度中被構建。
30. 閉包是一個圖中沒有出邊的頂點子集。閉包問題是找到帶權圖中使得權之和最大或最小的子集。
31. 基於拓撲排序的性質，無環圖的最短路問題和最長路徑問題可以線上性時間內解決。
32. 對於非無環圖，最短路需要用復雜度為O(|E|+|V|log|V|)的戴克斯特拉演算法或O(|V||E|)的貝爾曼-福特演算法等。最長路徑則是一個NP困難問題。
33. 無環圖的偏序關係可以在排程有前後順序限制的系統任務中發揮作用。
34. 排程問題的一個重要種類是串聯需要更新的物件，例如電子試算表中某個儲存格的計算公式依賴於其他儲存格，或在程式原始碼被修改後重新編譯目標文件。
35. 依賴圖記錄了這種更新依賴關係。其每個頂點對應一個需要被更新的物件，邊則表示更新的關係。
36. 依賴圖中的環被稱為環狀依賴。環狀依賴通常是不被允許出現的，因為不能保證圈內任務排定順序的一致性。
37. 無環的依賴圖即為無環圖。
38. 舉例來説，當電子試算表中一個儲存格的值發生改變，其他直接或間接依賴於該儲存格的所有儲存格的值都需要被重新計算。
39. 當一個儲存格的值取決於另外一個儲存格時，兩個儲存格之間則有依賴關係。
40. 每個被依賴儲存格的值的計算過程都必須先於使用它的表達式執行。
41. 使用依賴圖的拓撲排序來排程任務使得在每個儲存格的值都僅被重新計算一次的情況下，整個工作表都能被更新。
42. 類似的任務排程場景出現在程式原始碼編譯的makefile和最佳化電腦程式底層執行的指令排程中。
有向圖：探索有方向性的資料結構
有向圖是一種數學資料結構，由頂點和邊組成，其中邊具有方向。它不同於無向圖，那裡的邊沒有方向，也不同於超圖，那裡的邊可以連接多於兩個頂點。
頂點和邊
有向圖中的頂點通常被稱為節點，而邊表示頂點之間的關係。一條有向邊從一個稱為「源節點」的頂點開始，並指向另一個稱為「目標節點」的頂點。邊通常用箭頭符號 (→) 表示。
特性
有向圖具有以下關鍵特性：
| 特性 | 説明 |
|---|---|
| 頂點的度 | 一個頂點的度由其出邊數和入邊數之和定義。 |
| 強連通性 | 圖中的所有頂點都能通過有向路徑相互到達，稱為強連通性。 |
| 弱連通性 | 圖中的所有頂點都能通過無向路徑相互到達，稱為弱連通性。 |
| 循環 | 一條從頂點開始並回到同個頂點的有向路徑稱為循環。 |
表示法
有向圖可以用以下方式表示：
延伸閲讀…
圖(數學) – 維基百科，自由的百科全書
有向圖與無向圖的表示方式
- 鄰接矩陣：一個矩陣，其中元素表示源頂點和目標頂點之間的邊的權重或存在。
- 鄰接清單：一個清單，其中每個項對應一個源頂點，後跟其所有出邊的目標頂點清單。
應用
有向圖在許多實際情況中都有應用，包括：
- 社羣網路：建模使用者之間的跟蹤關係。
- 交通網路：建模道路和鐵軌之間的連接。
- 流程圖：可視化業務作業的流程。
運算法
有向圖中使用許多運算法，包括：
- 深度優先搜尋 (DFS)：一種通過遞迴或堆疊探索圖中節點的搜尋方法。
- 廣度優先搜尋 (BFS)：一種通過佇列探索圖中節點的搜尋方法。
- 最短路徑演算法：例如 Dijkstra 演算法，用於尋找兩節點之間的最短路徑。
- 拓樸排序：將頂點安排成線性序列，使得任何邊的源頂點總是位於其目標頂點之前。