深さ優先探索アルゴリズム (DFS)

7.1 DFSアルゴリズムの作動原理

深さ優先探索 (Depth-First Search, DFS)は、グラフを巡回または探索するアルゴリズムだよ。スタートの頂点から始めて、行けるところまで深く進んで、行き止まりになったら戻って、他の頂点を巡回する感じ。

アルゴリズムの手順:

1. 選んだスタートの頂点から始めて、訪れたとマークするんだ。
2. 最初の未訪問の隣接頂点を探索する。
3. その隣接頂点に対してステップ1と2を繰り返す。
4. 現在の頂点の隣接が全部訪問済みなら、前の頂点に戻って(backtrack)続けるんだ。
5. スタート地点から到達可能な頂点がすべて訪問されるまで、このプロセスを繰り返すんだ。

ビジュアル化:

DFSの時間と空間の計算量:

時間計算量:

O(V + E)、ここで V は頂点の数、E は辺の数だよ。

グラフの各ノードと各辺は一度ずつ訪れるんだ。

空間計算量:

O(V)、コールスタックまたは明示的なスタックを使って頂点を保存し、状態を管理する配列（訪問済み頂点）も使うからね。

7.2 再帰を使ったDFSの実装

まずは再帰を使ってDFSを実装してみよう—コードがきれいでコンパクトになるよ。

再帰的実装のDFS:

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # ノードの処理
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
# 使い方の例:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_recursive(graph, 'A')

7.3 スタックを使ったDFSの実装

再帰なしの場合、訪問済みの頂点リストを保持する必要があるため、コードは少し長くなるよ。

スタックを使ったイテレーティブなDFSの実装:

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
        
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # ノードの処理
        
            for neighbor in reversed(graph[vertex]):  # 正しい巡回順のために逆順
                if neighbor not in visited:
                    stack.append(neighbor)
        
# 使い方の例:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_iterative(graph, 'A')

7.4 DFSを使って解決できる問題の例

DFSを使って解決できるクラシックな問題の例:

1. 迷路の道探し:

スタート地点からゴール地点までの迷路の道を見つけるために使うんだ。

応用:

ビデオゲームやロボット工学で、迷路や複雑な空間のナビゲーションに使われるよ。

2. グラフの連結性チェック:

グラフが連結しているかどうか（任意の2つの頂点の間に道があるか）を確認するんだ。

応用:

ネットワーク分析でネットワークの連結性をチェックするのに使うよ。

3. トポロジカルソート:

有向非巡回グラフ（DAG）の頂点を、任意の辺(u, v)があるとき、頂点uが頂点vの前に来るように順序付けるんだ。

応用:

コンパイラで依存関係やタスクを順序付けるのに使われるよ。

4. グラフのサイクル検出:

グラフがサイクルを含んでいるかどうかをチェックするんだ。

応用:

依存関係の分析でサイクル依存を検出するのに使うよ。

5. 迷路生成:

ランダムな迷路を生成するためにDFSを使うんだ。

応用:

ゲームやエンターテイメントアプリで迷路を作るのに使われるよ。