有向無環圖 (DAG)

定義

在計算機科學和數學中，有向無環圖 (DAG) 指一種無向迴圈的有向圖。

說明

在圖論中，圖指一組透過稱為邊的直線連線的頂點。在有向圖或有向無環圖中，每條邊都與從起始頂點到結束頂點的方向相關聯。如果我們沿著邊的方向行進，並且發現沿著任何路徑都沒有形成閉合迴路，我們稱之為無有向迴圈。形成的圖是有向無環圖。

DAG 始終按照拓撲順序排列，即對於圖中的每條邊，邊的起始頂點在序列中的出現早於邊的結束頂點。

示例

在上面的有向圖中，如果我們查詢自任意節點（例如 u）的路徑，我們將永遠找不到返回 u 的路徑。因此，這是一個 DAG。

應用領域

DAG 的一些主要應用領域有 −

• 計算機網路中的路由

• 作業排程

• 資料處理

• 系譜

• 引文圖

Moumita

更新於：22-2月-2021

14K+ 瀏覽次數

開始你的 職業生涯

完成課程認證

開始