無向グラフのDFS(002)

はじめに

前回のDFSを起点に派生コードを使って学習。
スランプ対策の鉄則は、どんなにスランプ状態でも絶対に分かるものを沢山持っていることですからね。

まずは、DFSを得意分野にしておきます。

アルゴリズム一覧

無向グラフのDFS

【基本形】
【基本形からの派生01->グラフのノード数をカウント】
【基本形からの派生02->グラフの経路をリストとして出力】
【基本形からの派生03->サイクルの検出】
【基本形04->グラフのノード数と経路のリストを出力】
【基本形05->グラフ内の最長経路を見つける】
【基本形06->グラフ内の最短経路を見つける】
【基本形07->特定のノードから他のすべてのノードへの経路を出力】

基本形04->グラフのノード数と経路のリストを出力

dfs.py

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

    count = 1  # 現在のノードをカウント（初期値は1）

    for neighbor in graph[node]:  # 現在のノードの隣接ノードをループ
        if neighbor not in visited:  # 隣接ノードが未訪問の場合
            sub_count, _ = dfs_count_and_path(graph, neighbor, visited, path)  # 再帰的にDFSを呼び出す
            count += sub_count  # サブツリーからのカウントを加算

    return count, path  # 訪問したノードの総数とパスを返す

if __name__=="__main__":
    # グラフの定義（隣接リスト形式）
    graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A'],
        'D': ['B'],
        'E': ['B']
    }

    # DFSを実行
    count, path = dfs_count_and_path(graph, 'A')

    print("訪問したノードの個数:", count)
    print("訪問した経路:", path)

基本形05->グラフ内の最長経路を見つける

dfs.py

def dfs_longest_path(graph, node, visited=None, path=None):
    if visited is None:
        visited = set()
    if path is None:
        path = []

    visited.add(node)
    path.append(node)

    longest_path = list(path)  # 現在のパスを長さ比較用にコピー

    for neighbor in graph[node]:
        if neighbor not in visited:
            current_path = dfs_longest_path(graph, neighbor, visited, path)
            if len(current_path) > len(longest_path):
                longest_path = current_path  # 最長経路を更新

    path.pop()  # バックトラック
    visited.remove(node)  # バックトラック

    return longest_path

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

    longest_path = dfs_longest_path(graph, 'A')
    print("最長経路:", longest_path)

基本形06->グラフ内の最短経路を見つける

dfs.py

def dfs_shortest_path(graph, current_node, target_node, visited=None, path=None):
    if visited is None:
        visited = set()
    if path is None:
        path = []

    visited.add(current_node)
    path.append(current_node)

    if current_node == target_node:  # 目的のノードに到達した場合
        return list(path)  # 現在のパスを返す

    shortest_path = None  # 最短経路を初期化

    for neighbor in graph[current_node]:
        if neighbor not in visited:
            current_path = dfs_shortest_path(graph, neighbor, target_node, visited, path)
            if current_path:  # 有効な経路が見つかった場合
                if shortest_path is None or len(current_path) < len(shortest_path):
                    shortest_path = current_path  # 最短経路を更新

    path.pop()  # バックトラック
    visited.remove(current_node)  # バックトラック

    return shortest_path

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

    start_node = 'A'
    target_node = 'F'
    
    shortest_path = dfs_shortest_path(graph, start_node, target_node)

    if shortest_path:
        print("最短経路:", shortest_path)
    else:
        print("目的のノードに到達できません。")

基本形07->特定のノードから他のすべてのノードへの経路を出力

dfs.py

def dfs_all_paths_from_node(graph, current_node, target_node, visited=None, path=None):
    if visited is None:
        visited = set()
    if path is None:
        path = []

    visited.add(current_node)
    path.append(current_node)

    # 目的のノードに到達した場合
    if current_node == target_node:
        print("訪問した経路:", path)

    for neighbor in graph[current_node]:
        if neighbor not in visited:
            dfs_all_paths_from_node(graph, neighbor, target_node, visited, path)

    # バックトラック
    path.pop()
    visited.remove(current_node)

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

    start_node = 'A'

    # 各ノードに対して経路を探索
    for target_node in graph.keys():
        if target_node != start_node:  # 開始ノード自身は除外
            print(f"'{start_node}' から '{target_node}' への経路:")
            dfs_all_paths_from_node(graph, start_node, target_node)
            print()  # 改行

次回以降の方針

少しずつプログラムが煩雑になってきたので、クラス化します。