問題概要
ソースからターゲットへの全経路探索という課題では、有向無環グラフ（DAG）において、ソースノード（通常はノード 0）からターゲットノード（通常は最後のノード）へのすべての可能な経路を列挙します。グラフは隣接リスト形式で表され、graph[i] はノード i から直接到達可能なノードのリストを示します。
入出力例
入力：
graph = [[1,2],[3],[3],[]]
出力：
[[0,1,3],[0,2,3]]
説明：
- ノード
0からノード1と2に移動可能。 - ノード
1からノード3に移動可能。 - ノード
2からノード3に移動可能。 - 結果として、
[0,1,3]と[0,2,3]の2つの経路が存在する。
解法の概要
グラフは無環であるため、経路にループが生じることはありません。この特性を活かし、深さ優先探索（DFS）を用いてすべての経路を探索します。手順は以下の通りです。
- 初期化：ソースノード
0から探索を開始し、初期経路は[0]とします。 - 再帰的探索：現在のノードの隣接ノードを順に処理し、各ノードを経路に追加して再帰的に探索を進める。
- 終了条件：現在のノードがターゲットノード（最後のノード）に到達した場合、その経路を結果リストに保存。
- バックトラック：再帰呼び出しから戻る際、経路から現在のノードを削除し、他の経路の探索を試みる。
実装コード
class PathFinder:
def find_all_routes(self, adjacency_list: List[List[int]]) -> List[List[int]]:
def explore(current_node: int, current_path: List[int]):
if current_node == destination:
all_routes.append(current_path[:])
return
for next_node in adjacency_list[current_node]:
current_path.append(next_node)
explore(next_node, current_path)
current_path.pop()
destination = len(adjacency_list) - 1
all_routes = []
explore(0, [0])
return all_routes
コードの解説
- explore関数：再帰的に深さ優先探索を実行。
- 引数：
current_nodeは現在処理中のノード、current_pathは現在の経路を保持。 - 終了条件：
current_nodeがターゲットdestinationに一致した場合、経路を結果リストにコピーして保存。 - 再帰処理：隣接ノードを順に追加し、再帰呼び出しを実行。戻る際には末尾のノードを削除（バックトラック）。
- 初期化：
destinationをグラフの最後のノードに設定し、all_routesで結果を蓄積。 - 探索開始：初期ノード
0から探索を開始し、初期経路[0]を渡す。
計算量の分析
- 時間計算量：O(N * 2^N) （Nはノード数）。最悪の場合、各ノードがすべての後続ノードと接続される場合、経路数は指数関数的に増加。
- 空間計算量：O(N)。再帰スタックの深さは最大でN、経路の保存に必要なメモリは O(N * P)（Pは経路数）。
このアプローチはDFSを用いて効率的に経路を探索し、バックトラックにより冗長な計算を防ぎます。DAGにおける経路探索問題に適しています。