1. グラフのループを判定したい
エッジのリストを受け取って「このグラフにループはあるか」を判定したい場面があります。
トポロジカルソートの前処理、依存関係の検証、スケジューラの循環チェックなど、グラフを扱うコードでは頻出の問題です。
このテーマは有向グラフのサイクル検出、英語では Cycle Detection in Directed Graphs と呼ばれます1。
1.1. サイクルとは何か
有向グラフのサイクルは、向きを守ったまま元のノードに戻れる経路を指します2。
無向グラフのサイクルとは定義が異なる点に注意が必要です。
たとえば次のエッジ列を見てください。
a b
b c
b d
d aa から b、b から d、d から a と辿れるので、このグラフにはサイクルがあります。
一方、b から c に向かうエッジはあっても c から戻る経路がなければ、c はサイクルに関与しません。
2. DFSと3色アルゴリズム
サイクルを検出する標準的な手法は、深さ優先探索 DFS とノードへの3段階の状態付けを組み合わせたものです。
各ノードに次の3種類の状態を割り当てます。
- 未訪問——まだ探索を始めていない
- 探索中——現在たどっている経路上にある
- 完了——そのノードより先の全ノードを調査済み
DFSで隣接ノードを再帰的にたどるとき、「探索中」状態のノードに再び到達したら、今まさに追いかけている経路の中を周回していることになります。
それがサイクルの証拠です3。
「完了」状態のノードはすでに調査済みなので、そこで探索を打ち切れます。
このアルゴリズムは3色塗り分け法とも呼ばれます4。
計算量は O(V + E) で、V はノード数、E はエッジ数です。
グラフ全体を一度なめるだけで判定が終わります5。
2.1. Common Lisp での実装
データ形式として、インデックス i からのエッジ先リストを (aref graph i) で取得できる隣接リスト表現を使います。
#(NIL NIL NIL (4 3) (4 3))Code language: PHP (php)これはインデックス3と4がそれぞれ4と3に向かうエッジを持ち、他のノードは出次数ゼロであることを表します。
(defun has-cycle-p (graph)
(let* ((n (length graph))
;; 0 = 未訪問, 1 = 探索中, 2 = 完了
(state (make-array n :initial-element 0)))
(labels ((visit (v)
(cond
;; 探索中のノードに戻ってきた → サイクルあり
((= (aref state v) 1) t)
;; 完了済み → サイクルなし
((= (aref state v) 2) nil)
(t
(setf (aref state v) 1)
(let ((found (some #'visit (aref graph v))))
(setf (aref state v) 2)
found)))))
(loop for i below n
thereis (visit i)))))Code language: Lisp (lisp)some は要素のいずれかで述語が真になれば即座に T を返します6。
サイクルが見つかった時点で探索を打ち切れるので、最悪ケース以外では早期終了できます。
2.2. 動作確認
インデックス3が4へ、4が3へ向かうグラフです。3 → 4 → 3 の循環が存在します。
(has-cycle-p #(nil nil nil (4 3) (4 3)))
;; => TCode language: Lisp (lisp)インデックス3から4へ一方向のみで、4からどこにも戻れないケースです。
(has-cycle-p #(nil nil nil (4) nil))
;; => NILCode language: Lisp (lisp)先ほどの a b b c b d d a を数値インデックスに変換すると次のようになります。
a=0, b=1, c=2, d=3(has-cycle-p #((1) (2 3) nil (0)))
;; => T ; 0 → 1 → 3 → 0 で戻るCode language: Lisp (lisp)3. 文字列ノードへの対応
実際のデータが記号や文字列で与えられる場合は、前処理として名前とインデックスの対応表を作り、隣接リストに変換してから渡します。
(defun build-graph (edges)
"((\"a\" \"b\") (\"b\" \"c\") ...) を受け取り隣接リスト配列を返す"
(let* ((nodes (remove-duplicates
(loop for (u v) in edges append (list u v))
:test #'equal))
(index (let ((h (make-hash-table :test #'equal)))
(loop for n in nodes for i from 0
do (setf (gethash n h) i))
h))
(size (hash-table-count index))
(graph (make-array size :initial-element nil)))
(dolist (edge edges)
(let ((u (gethash (first edge) index))
(v (gethash (second edge) index)))
(push v (aref graph u))))
graph))Code language: Lisp (lisp)(has-cycle-p
(build-graph '(("a" "b") ("b" "c") ("b" "d") ("d" "a"))))
;; => TCode language: Lisp (lisp)3.1. トポロジカルソートとの関係
サイクルのない有向グラフは DAG と呼ばれ7、トポロジカルソートが定義できるのはこの種のグラフだけです。
has-cycle-p が NIL を返すグラフであれば、同じ DFS の枠組みで完了順の逆順を取るとトポロジカル順序が得られます8。
サイクル検出はその前提として機能します。
- サイクル検出の応用先は広く、タスクスケジューリング、ビルドシステムの依存解決、コンパイラの循環インポート検出などが代表例として挙げられる。 – Detect Cycle in a Directed Graph – GeeksforGeeks
- 無向グラフでは「訪問済みの親ノードに戻ってきた」だけでサイクルとみなせるが、有向グラフではその判定が成立しない。辺の向きがあるため、別の経路から同じノードを再訪しても必ずしもサイクルではないからだ。 – Detect Cycle in a Directed Graph – GeeksforGeeks
- DFS の文脈ではこのエッジを後退辺（バックエッジ）と呼ぶ。有向グラフにサイクルが存在するのは DFS がバックエッジを発見する場合に限り、逆も成立する。 – Depth First Search – cp-algorithms
- 未訪問を白、探索中を灰色、完了を黒と表現する命名は Cormen らの “Introduction to Algorithms”（通称 CLRS）に由来する。3色でノードを塗り分けるイメージがそのままアルゴリズムの挙動を示している。 – Detecting Graph Cycles With Depth-First Search – DEV Community
- O(V + E) は線形時間を意味する。DFS は各ノードを1回、各エッジを1回だけ処理するため、ノード数と辺数の和に比例する時間でアルゴリズムが完了する。 – Detect Cycle in a Directed Graph – GeeksforGeeks
- some は ANSI Common Lisp 標準で定義されており、述語が真を返した時点でリストの残りを評価しないことが仕様として保証されている。 – CLHS: Function SOME – LispWorks
- DAG は Directed Acyclic Graph の略。辺をたどってもいかなる閉じた経路も形成されない有向グラフを指す。トポロジカル順序が存在するのはこの種のグラフに限られ、任意の DAG には少なくとも1つのトポロジカル順序が存在することが証明されている。 – Topological sorting – Wikipedia
- DFS でノードの探索が完了した時刻を記録し、その降順に並べるとトポロジカル順序になる。この手法は Tarjan のアルゴリズムでも利用されており、サイクル検出とトポロジカルソートが同一の DFS パスで解ける理由でもある。 – Topological Sorting – GeeksforGeeks