有向非巡回グラフ（DAG）とトポロジカルソート - Qiita

有向非巡回グラフ（DAG） 有向非巡回グラフ（Directed Acyclic Graph: DAG）とは、閉路のない有向グラフのことである。サイクルが存在しないため、ある頂点から同じ頂点に戻ってこれないという特徴がある。 有向非巡回グラフは要素の因果関係や物事の依存関係をモデル化するのに有効である。例えばあるタスクを行う前に別のタスクを完了させておく必要がある場合、タスクを頂点、順序の制約を有向辺とみなすと、各タスクの依存関係を有向非巡回グラフで表現することができる。また後述するトポロジカルソートを使用することで、制約条件に従ってタスクを完了させるための適当な順序を得ることができる。ただしジャンケンのグー・チョキ・パーのように依存関係（強さの順序）がサイクルを形成するような場合、巡回グラフとなるため順序付け（トポロジカルソート）を行うことはできない。 トポロジカルソート トポロジカルソー