有向・無向グラフにおけるサイクル検出
有向グラフと無向グラフの両方でサイクルを検出する方法を学びます。色を使用したDFSベースの検出、後退辺、Union-Findアプローチを明確な例で理解します。
Graph Properties
詳細な説明
グラフのサイクル検出
サイクルは、あるノードから辺を辿って同じノードに戻ることができる場合に存在します。サイクル検出はデッドロック検出、依存関係の検証、トポロジカルソートの可否判定に不可欠です。
無向グラフでのサイクル検出
無向グラフでは、DFS中に現在のノードの親ではない訪問済みノードに遭遇した場合にサイクルが検出されます。
Union-Findアプローチ: 各辺(u, v)について、uとvが同じセットにあるかチェック。はいの場合、この辺を追加するとサイクルが作成されます。
有向グラフでのサイクル検出
有向グラフでは、三色アルゴリズムを使用します：
- 白（未訪問） — まだ発見されていない
- 灰（処理中） — 現在探索中（再帰スタック上）
- 黒（完了） — 完全に探索済み
後退辺 — 灰色のノードから別の灰色のノードへの辺 — がサイクルを示します。
時間計算量
両方のアプローチとも**O(V + E)**で実行されます。
重要性
- DAG検証 — トポロジカルソートは非循環有向グラフでのみ動作
- デッドロック検出 — サイクルを持つリソース割り当てグラフはデッドロックを示す
- パッケージマネージャ — 循環依存を検出して報告する必要がある
ユースケース
ビルドシステム（Make、Gradle、Bazel）はビルド順序を計算する前に循環依存がないことを確認するためにサイクル検出を使用します。OSはリソース割り当てグラフのサイクルをチェックしてデッドロックを検出します。パッケージマネージャは循環依存チェーンをチェックします。