無向グラフのDFS(001)

はじめに

前回演習した競技プログラミングの問題で、DFSの理解が苦戦したので、迷ったときは初心に戻り基本的なところからやり直そうと思います。

競技プログラミングは非常に有益だけど、問題解くことを目的化すると今までのように失敗してしまうのでアルゴリズムだけを見直していきます。

アルゴリズム一覧

無向グラフのDFS

【基本形】
【基本形からの派生01->グラフのノード数をカウント】
【基本形からの派生02->グラフの経路をリストとして出力】
【基本形からの派生03->サイクルの検出】

DFS(基本形)

dfs.py

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(node)
    print(node, end=' ')  # 訪問したノードを出力
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)


if __name__=="__main__":
    graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }
    dfs(graph, "A")

DFS(基本形からの派生01->グラフのノード数をカウント)

dfs.py

def dfs_count(graph, node, visited=None):
    if visited is None:
        visited = set()  # 訪問済みのノードを追跡するためのセットを初期化
    
    visited.add(node)  # 現在のノードを訪問済みとしてマーク
    count = 1  # 現在のノードをカウント（初期値は1）

    for neighbor in graph[node]:  # 現在のノードの隣接ノードをループ
        if neighbor not in visited:  # 隣接ノードが未訪問の場合
            count += dfs_count(graph, neighbor, visited)  # 隣接ノードに対して再帰的にDFSを呼び出し、カウントを加算
    
    return count  # 訪問したノードの総数を返す

# 使用例
graph = {
    'A': ['B', 'C'],  # ノードAはBとCに接続
    'B': ['A', 'D', 'E'],  # ノードBはA、D、Eに接続
    'C': ['A'],  # ノードCはAに接続
    'D': ['B'],  # ノードDはBに接続
    'E': ['B', 'F'],  # ノードEはBとFに接続
    'F': ['E']  # ノードFはEに接続
}

total_nodes = dfs_count(graph, 'A')  # ノードAからDFSを開始し、訪問したノードの総数を取得
print(f"Total nodes visited: {total_nodes}")  # 訪問したノードの総数を出力

DFS(基本形からの派生02->グラフの経路をリストとして出力)

dfs.py

def dfs_path(graph, node, visited=None, path=None):
    if visited is None:
        visited = set()  # 訪問済みのノードを追跡するためのセットを初期化
    if path is None:
        path = []  # 訪問したノードのパスを格納するリストを初期化
    
    visited.add(node)  # 現在のノードを訪問済みとしてマーク
    path.append(node)  # 現在のノードをパスに追加

    for neighbor in graph[node]:  # 現在のノードの隣接ノードをループ
        if neighbor not in visited:  # 隣接ノードが未訪問の場合
            dfs_path(graph, neighbor, visited, path)  # 再帰的にDFSを呼び出す
    
    return path  # 訪問したノードのパスを返す

# 使用例
graph = {
    'A': ['B', 'C'],  # ノードAはBとCに接続
    'B': ['A', 'D', 'E'],  # ノードBはA、D、Eに接続
    'C': ['A'],  # ノードCはAに接続
    'D': ['B'],  # ノードDはBに接続
    'E': ['B', 'F'],  # ノードEはBとFに接続
    'F': ['E']  # ノードFはEに接続
}

all_paths = dfs_path(graph, 'A')  # ノードAからDFSを開始し、全てのパスを取得
print("Path taken:", all_paths)  # 訪問したパスを出力

DFS(基本形からの派生03->サイクルの検出)

dfs.py

def has_cycle(graph, node, visited=None, parent=None):
    if visited is None:
        visited = set()
    
    visited.add(node)

    for neighbor in graph[node]:
        # 隣接ノードが未訪問であれば再帰的に探索
        if neighbor not in visited:
            if has_cycle(graph, neighbor, visited, node):
                return True
        # 隣接ノードが訪問済みかつ親でない場合はサイクルあり
        elif parent is not neighbor:
            return True
    
    return False

# 使用例
graph_with_cycle = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'D'],  # サイクルが形成される
    'D': ['B', 'C'],
    'E': ['B']
}

cycle_exists = has_cycle(graph_with_cycle, 'A')
print(f"Cycle exists: {cycle_exists}")