RSS
Search

深さ優先探索

数学 Published at March 24, 2025, 4:01 a.m. by admin@senrigan.org

できるだけ深く進んで行き止まりだったらバックトラックする方法

特徴

  • スタックで実装する
  • 再帰とも相性が良い
  • メモリ使用量少ない
  • ツリー構造の探索向き
  • 最短経路は不向き

動作

  1. 出発点を決める
  2. 未訪問のお隣さんを訪問
  3. 突き進む
  4. 行き止まりだったら一歩手前の分岐まで戻る
  5. すべてのノードを訪問するまで繰り返す

実装

スタック

def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node)
            stack.extend(reversed(graph[node]))

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'D'],
    'D': ['B', 'C', 'F'],
    'E': ['B', 'F'],
    'F': ['D', 'E'],
}

dfs(graph, 'A')

再帰

def rdfs(graph, node, visited):
    if node in visited:
        return

    visited.add(node)
    print(node)

    for neighbor in graph[node]:
        rdfs(graph, neighbor, visited)

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'D'],
    'D': ['B', 'C', 'F'],
    'E': ['B', 'F'],
    'F': ['D', 'E'],
}

visited = set()
rdfs(graph, 'A', visited)

グラフ

dfs.svg