有向非巡回グラフ（DAG）とは？
有向非巡回グラフ（DAG）とは、辺に向きがあり、どの頂点から出発しても矢印をたどって元へ戻れない（閉路がない）グラフ。「AはBより先」という順序関係を表現でき、作業の前後関係や部品の依存関係のモデル化に適する。
ゆうこうひじゅんかいぐらふ
有向非巡回グラフ（DAG）の意味
辺に向きがあり、どの頂点から出発しても矢印をたどって元へ戻れない（閉路がない）グラフ。「AはBより先」という順序関係を表現でき、作業の前後関係や部品の依存関係のモデル化に適する。
有向非巡回グラフ（DAG）の具体例
ソフトウェアのビルドで、部品Aを作ってから部品Bを作るという依存関係を頂点と矢印で表したもの。閉路がないことが保証されていれば、必ずどこかから順に作り始められると分かる。
有向非巡回グラフ（DAG）は試験でどう引っ掛けられる？
閉路がないことと「木である」ことは別物。有向非巡回グラフでは1つの頂点に入ってくる辺が複数あってよいので、親が1つという木の条件を満たすとは限らない点を混同しやすい。
有向非巡回グラフ（DAG）と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。