読み方：ゆうこうひじゅんかいグラフ

有向非巡回グラフ【DAG】Directed Acyclic Graph

概要

有向非巡回グラフとは、グラフ構造の一種で、辺に向きがあり、かつ一度進むと同じ頂点に戻る循環的な経路が存在しないもの。物事の順序関係や依存関係を表すのに適している。

グラフ構造とは、複数の頂点と、それらを一対一に結ぶ辺から構成される数学的構造である。有向グラフでは、各辺に方向が定められており、ある頂点から別の頂点へ一方向にのみ進むことができる。また、非巡回とは、どの頂点から出発しても、辺の向きに従って進んだ結果、再び元の頂点に戻る経路、すなわち閉路が存在しないことを意味する。この二つの性質を併せ持つ構造が有向非巡回グラフである。

有向非巡回グラフは、順序関係や依存関係を表現するのに適しており、ある作業が別の作業に依存している場合、その依存方向を辺の向きで示すことができる。例えば、家を建てる手順で、基礎工事が終わらなければ柱を立てられないといった「前の工程が終わらないと次へ進めない」という制約を表現できる。閉路がないため、依存関係が循環して矛盾することがない。

有向非巡回グラフの性質を利用して、すべての頂点を依存関係を保ちながら一列に並べる「トポロジカルソート」という操作を行うことができる。すべての辺が同じ方向へ向かうように頂点を並べ替えるアルゴリズムで、複雑に絡み合った依存関係の中から、最初に行うべき作業から最後に行うべき作業までの最適な実行順序を数学的に導き出すことができる。

コンピュータ上での応用としては、データの処理手順やソフトウェアのビルド手順の管理などに用いられている。複数の処理を並行して進める際、どの計算結果が他の計算に必要かを明確に定義できるため、効率的な分散処理が可能となる。近年では、ブロックチェーンに代わる新しい分散台帳技術や、機械学習におけるニューラルネットワークの計算経路の表現としても利用されている。