依存関係の「循環参照」をグラフ理論で解く：再帰的探索によるデッドロック検出
大規模なWBS（Work Breakdown Structure）やプロジェクト管理ツールをVBAで構築する際、最もエンジニアを悩ませるのが「タスク間の依存関係（先行・後続タスク）」の整合性だ。
「タスクAの完了がタスクBの前提であり、タスクBの完了がタスクCの前提である……そして巡り巡ってタスクCの完了がタスクAの前提になっている」
このような循環参照（Circular Dependency）が発生した瞬間、プロジェクトのスケジュール計算エンジンは無限ループに陥り、Excelはフリーズし、ユーザーの信頼は地に落ちる。
今回は、この厄介なデッドロック問題に対し、グラフ理論（有向グラフの閉路検出）を応用した高度な再帰的探索アルゴリズムを用いて、VBA上で完璧に検知・排除するアーキテクチャを伝授する。
—
なぜ「愚直なチェック」では破綻するのか
多くの開発者は、依存関係を設定する際に「直近の親タスクだけ」を見たり、テーブルを上から順に舐めるだけの浅いバリデーションを実装しがちだ。
しかし、次のような多段にわたる依存関係を想像してほしい。
[タスク1] → [タスク2] → [タスク3] → [タスク4]
↑ │
└───────────────────────────────────┘
タスク4に対して新たに「タスク1を先行タスクとして追加する」という操作を行った場合、局所的なチェックではこのループを検知できない。データ構造全体を「有向グラフ（Directed Graph）」と捉え、数学的に閉路（Cycle）が存在するかを判定するエンジンが不可欠なのだ。
—
グラフ理論的アプローチ：3色制約（Three-Color Marking）による深さ優先探索（DFS）
循環参照の検出において、最もエレガントかつ確実な手法が深さ優先探索（DFS: Depth-First Search）と3色制約（White-Gray-Black Algorithm）の組み合わせである。
グラフの各ノード（タスク）の状態を以下の3つに分類して追跡する。
1. 白（White / 未訪問）: まだ探索していないノード。
2. 灰色（Gray / 訪問中・処理中）: 現在の探索パス（祖先ノードの系譜）に含まれているノード。この「灰色」に再度到達した瞬間、循環参照（デッドロック）の発生が確定する。
3. 黒（Black / 探索完了）: このノードからの全探索が正常に完了し、循環がないことが確認されたノード。
このアルゴリズムをVBAのDictionaryと再帰呼び出しで実装することで、数千件規模のWBSであっても一瞬でデッドロックを検知できる。
—
プロダクションコード：循環検出エンジンの実装
実務でそのまま組み込める、堅牢で保守性の高いVBAモジュールを提供する。
このコードは、ワークシート上の「タスクID」と「先行タスクID（カンマ区切り等）」のリストを読み込み、循環参照が含まれている場合にそのパスを特定してイミディエイトウィンドウに出力する。
Option Explicit
‘ =====================================================================
‘ クラス名 / モジュール: M02_CycleDetector
‘ 概要: グラフ理論（DFSと3色マーキング）を用いた依存関係の循環検出エンジン
‘ =====================================================================
‘ ノードの状態定義
Private Const STATE_WHITE As Long = 0 ‘ 未訪問
Private Const STATE_GRAY As Long = 1 ‘ 訪問中（現在の探索パス）
Private Const STATE_BLACK As Long = 2 ‘ 探索完了
Public Sub RunCycleDetection()
Dim ws As Worksheet
Set ws = ThisWorkbook.Sheets(“WBS”)
‘ 1. データの読み込みとグラフ（隣接リスト）の構築
Dim adjList As Object
Set adjList = CreateObject(“Scripting.Dictionary”)
Dim lastRow As Long
lastRow = ws.Cells(ws.Rows.Count, “A”).End(xlUp).Row
If lastRow < 2 Then
MsgBox "検証対象のタスクデータが存在しません。", vbExclamation
Exit Sub
End If
Dim i As Long
Dim taskId As String
Dim predecessors As String
Dim predArray() As String
Dim j As Long
' データのマッピング (Key: タスクID, Value: 先行タスクIDの配列を格納したCollection)
For i = 2 To lastRow
taskId = Trim(CStr(ws.Cells(i, 1).Value)) ' A列: タスクID
predecessors = Trim(CStr(ws.Cells(i, 2).Value)) ' B列: 先行タスクID (例: "T001,T002")
If Not adjList.Exists(taskId) Then
adjList.Add taskId, CreateObject("System.Collections.ArrayList")
End If
If predecessors <> “” Then
predArray = Split(predecessors, “,”)
For j = LBound(predArray) To UBound(predArray)
Dim pId As String
pId = Trim(predArray(j))
If pId <> “” Then
‘ 有向エッジの追加: taskId は pId に依存している（pId -> taskId）
‘ ※「先行タスクから後向タスクへの向き」でグラフを構築する場合
‘ ここでは「タスク -> その先行タスク」の方向に依存を定義
adjList(taskId).Add pId
End If
Next j
End If
Next i
‘ 2. 3色制約によるDFSの実行
Dim visited As Object
Set visited = CreateObject(“Scripting.Dictionary”)
Dim key As Variant
Dim hasCycle As Boolean
hasCycle = False
For Each key In adjList.Keys
If visited(key) = STATE_WHITE Or Not visited.Exists(key) Then
Dim pathStack As Object
Set pathStack = CreateObject(“System.Collections.ArrayList”)
If DFS(key, adjList, visited, pathStack) Then
hasCycle = True
Exit For
End If
End If
Next key
If hasCycle Then
MsgBox “致命的なエラー: 依存関係に循環参照（デッドロック）が検出されました。” & vbCrLf & _
“詳細はイミディエイトウィンドウを確認してください。”, vbCritical, “WBS整合性チェック”
Else
MsgBox “検証完了: 循環参照は検出されませんでした。スケジュール計算を実行可能です。”, vbInformation, “WBS整合性チェック”
End If
End Sub
‘ 深さ優先探索（DFS）による再帰的閉路検出
Private Function DFS(ByVal currentNode As String, ByRef adjList As Object, ByRef visited As Object, ByRef pathStack As Object) As Boolean
‘ 現在のノードを「訪問中（灰色）」に設定し、パスに追加
visited(currentNode) = STATE_GRAY
pathStack.Add currentNode
If adjList.Exists(currentNode) Then
Dim neighbor As Variant
Dim neighbors As Object
Set neighbors = adjList(currentNode)
For Each neighbor In neighbors
‘ グラフに定義されているが、マスター側にタスクが存在しない場合のハンドリング
If Not visited.Exists(neighbor) Then
visited(neighbor) = STATE_WHITE
End If
If visited(neighbor) = STATE_GRAY Then
‘ 【循環検出】 灰色ノードに再到達した場合、ここで閉路が成立
Debug.Print “— 循環参照（デッドロック）検出 —”
Dim cyclePath As String
cyclePath = “”
Dim idx As Long
Dim found As Boolean
found = False
For idx = 0 To pathStack.Count – 1
If pathStack(idx) = neighbor Then found = True
If found Then
cyclePath = cyclePath & pathStack(idx) & ” -> ”
End If
Next idx
cyclePath = cyclePath & neighbor
Debug.Print “閉路パス: ” & cyclePath
DFS = True
Exit Function
ElseIf visited(neighbor) = STATE_WHITE Then
‘ 未訪問の隣接ノードを再帰的に探索
If DFS(neighbor, adjList, visited, pathStack) Then
DFS = True
Exit Function
End If
End If
Next neighbor
End If
‘ 探索完了：スタックからポップし、「完了（黒）」にマーク
pathStack.RemoveAt pathStack.Count – 1
visited(currentNode) = STATE_BLACK
DFS = False
End Function
—
現場のアーキテクトが教える：実装上の重要ポイントと落とし穴
1. Scripting.Dictionary と .NET ArrayList の活用
VBA標準のコレクションはインデックスによる高速な順序制御や存在確認が弱いため、`Scripting.Dictionary`でノード管理を行い、探索パスのスタック構造には `.NET FrameworkのArrayList（`CreateObject(“System.Collections.ArrayList”)`）` を採用している。これにより、VBAでありながらO(N)の高速なパス追跡が可能になる。
2. 外部データベース/Excel連携時のトランザクション保護
UI側でユーザーが「先行タスク」をコンボボックス等でポチポチと追加・変更する都度、このバリデーションを走らせてはならない。「保存ボタン押下時」あるいは「一括インポート時」にバックグラウンドでこのグラフ検証を走らせ、不正なデータがモデル層（データベースや永続化シート）に書き込まれるのを完全にブロックする設計にすること。
3. エラーメッセージの親切心
単に「エラーです」と弾くだけでは、ユーザーは何を直せばいいか迷う。上記のコードがイミディエイトに出力するように、「どのタスクとどのタスクが輪っかを作っているのか（閉路パス）」を明確にログ化し、ユーザーへフィードバックインターフェースを提供することが、真に実用的なツールを作るプロの仕事である。
—
結びにかえて
VBAは「おもちゃのマクロ言語」ではない。適切なデータ構造とアルゴリズム（今回はグラフ理論）を適用すれば、エンタープライズ領域のプロジェクト管理システムに匹敵する堅牢なロジックを実装できる。
「動けばいいや」という場当たり的なコードを捨て、数学的裏付けのある堅牢なアーキテクチャで、あなたの業務自動化ツールをワンランク上のステージへ引き上げてほしい。
