無閉路有向グラフ(Directed acyclic graph)

グラフ中の有向閉路とは、エッジの向きに進んだときに、ぐるぐると回れてしまうような閉路を言う。今、有向グラフのうち、有向閉路を持たないグラフを無閉路有向グラフと呼ぶ。無閉路有向グラフにおいては、エッジの向きを無視すれば閉路は存在するものの、エッジの向きを考慮するとぐるぐる回れないようなグラフを含む。木はグラフの中の特殊型であるが、無閉路有向グラフは木よりも制約が弱く、一般的なグラフと木の中間的要素を有し、その特徴を用いた処理が可能である。

ＡＲＧは無閉路有向グラフである。

無閉路有向グラフにはトポロジカルソートが適用できる