在圖論中，如果一個有向圖從任意頂點出發(fā)無法經(jīng)過若干條邊回到該點，則這個圖是一個有向無環(huán)圖（DAG圖）。 因為有向圖中一個點經(jīng)過兩種路線到達另一個點未必形成環(huán)，因此有向無環(huán)圖未必能轉(zhuǎn)化成樹，但任何有向樹均為有向無環(huán)圖。

一、簡介

有向無環(huán)圖是圖論的重要概念，我們將首先介紹圖的概念和定義，隨后介紹有向圖，再逐漸引至有向無環(huán)圖（DAG）。值得一提的是，當DAG用于指代模型時一般指向貝葉斯網(wǎng)絡(luò)。

一個圖G是頂點V的有限集合以及邊E的多重集（每個連接兩個不一定不同的頂點），在這里我們表示為G=V∪E，即V和E的并集，而沒有寫作其一般表示G=( V, E)。 圖G=V∪E的大小由|E|表示的邊緣（edge）確定， G的順序是用|V|表示的頂點數(shù)。 下圖給出了一些簡單的示例：

而有向圖（diagraph）D是一組頂點V，連同?。╝rc）的多重集A表示的，寫作D=V∪A。

弧被表示為有序的頂點對，例如，a=(x,y)，其中x是a的尾部，y是a的頭部，而a則從尾部x到頭部y。 A_v^+， A_v^- 分別表示從v出發(fā)或鏈接到v的集合。 因此我們可以用A_v = A_v^v ∪ A_v^- 來表示從v出發(fā)或鏈接到v的弧的集合。頂點v∈V的入邊數(shù)量（in-degree）id(v)= d(v)^- 是 以v為頭的弧。 類似地，對于任何v∈V，出邊數(shù)量（out-degree） od(v)= d(v)^+是以v作為尾部的弧的數(shù)量。

對于每一個有向圖，以下性質(zhì)明顯成立：

下圖給出了一個具有弧a=(x,y)，b=(y,x)，...，的有向圖示例。

接下來我們需要引入環(huán)的概念。

我們定義開放路徑（open trial）為一條沒有頂點遍歷多次（所有頂點都不相同）的路徑。 在路徑P（v_0，v_n）中，頂點v_1, ... , v_{n-1}被稱為P（v_0，v_n）的內(nèi)部頂點。 如果除了v_0 = v_n外，其他所有的頂點都不相同，并且它包含至少一個邊，則我們稱其為一個環(huán)，也即是閉合路徑（closed trail）的定義。

下圖給出了一些簡單示例：

而一個圖G或有向圖D如果不包含（循）環(huán)（cycle），則稱它為無環(huán)圖（acyclic）。 一個無環(huán)圖G被稱為森林（forest），而只有一個組成部分的森林被稱為樹。

因此，我們可以很清晰的看到有向無環(huán)圖（DAG）的定義為：有向無環(huán)圖是沒有環(huán)的有向圖。

二、性質(zhì)

1. 能拓撲排序的圖，一定是有向無環(huán)圖；如果有環(huán)，那么環(huán)上的任意兩個節(jié)點在任意序列中都不滿足條件了。

2. 有向無環(huán)圖，一定能拓撲排序；（歸納法）假設(shè)節(jié)點數(shù)不超過 k 的 有向無環(huán)圖都能拓撲排序，那么對于節(jié)點數(shù)等于 k 的，考慮執(zhí)行拓撲排序第一步之后的情形即可。

三、判定

如何判定一個圖是否是有向無環(huán)圖呢？

檢驗它是否可以進行拓撲排序即可。當然也有另外的方法，可以對圖進行一遍 DFS，在得到的 DFS 樹上看看有沒有連向祖先的非樹邊（返祖邊）。如果有的話，那就有環(huán)了。