深さ優先探索（depth-first search: DFS）

深さ優先探索（depth-first search: DFS）#

  • 根ノードから子ノードへとどんどん深く探索していき、行き着いたらバックトラック（一歩逆戻り）して別のノードを探索する

  • 深さ優先探索 - Wikipedia

実装例#

グラフのDFS（再帰あり）#

計算量はノード数\(N\)とエッジ数\(E\)に対し \(O(N + E)\) 。各ノードを高々1回訪問し、各エッジを高々1~2回訪問するため

def dfs(graph: dict[int, list[int]], start: int):
    visited = set()  # 訪問済みの頂点を記録する

    def _dfs(v):
        visited.add(v)
        print(f"到達したnode: {v}, {visited=}")

        for next_v in graph[v]:
            if next_v not in visited:
                _dfs(next_v)

    _dfs(start)


graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0],
    3: [1],
    4: [1]
}
dfs(graph, 0)

到達したnode: 0, visited={0}
到達したnode: 1, visited={0, 1}
到達したnode: 3, visited={0, 1, 3}
到達したnode: 4, visited={0, 1, 3, 4}
到達したnode: 2, visited={0, 1, 2, 3, 4}

グラフのDFS（再帰なし）#

stackを使うことで再帰関数を使わない実装もできる

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

    while stack:
        v = stack.pop()

        if v in visited:
            continue

        visited.add(v)
        print(f"到達したnode: {v}, {visited=}")

        for next_v in graph[v]:
            if next_v not in visited:
                stack.append(next_v)

graph = {
    0: [1, 2], # 各頂点とつながる頂点たち
    1: [0, 3, 4],
    2: [0],
    3: [1],
    4: [1]
}
dfs_iterative(graph, 0)

到達したnode: 0, visited={0}
到達したnode: 2, visited={0, 2}
到達したnode: 1, visited={0, 1, 2}
到達したnode: 4, visited={0, 1, 2, 4}
到達したnode: 3, visited={0, 1, 2, 3, 4}

from typing import List


def get_adjacent_nodes(edges: List[list]) -> List[list]:
    """各nodeと隣接したnodeのリストを作る"""
    nodes = set(sum(edges, []))
    adjacent_nodes = []
    for node in nodes:
        adjacent_node = []
        for edge in edges:
            if node in edge:
                e = [e for e in edge if e != node][0]
                adjacent_node.append(e)
        adjacent_nodes.append(adjacent_node)
    return adjacent_nodes


def dfs(edges: List[list]):
    """深さ優先探索（depth-first search）"""
    adjacent_nodes = get_adjacent_nodes(edges)
    n_edge: int = len(set(sum(edges,[])))
    # その頂点を検知済みかどうかを表す配列
    searched: List[bool] = [False] * n_edge
    # 検知したがまだ訪問済みでない頂点の集合 (保留中の頂点の集合)
    todo: List[int] = []
    # root nodeをtodoに入れる
    searched[0] = True
    todo.append(0)
    while len(todo) > 0:
        target_node: int = todo.pop()
        print(f"searching a node '{target_node}'")
        for adj_node in adjacent_nodes[target_node]:
            if not searched[adj_node]:
                print(f"{adj_node} is found and enqueued to todo")
                todo.append(adj_node)
                searched[adj_node] = True


# 隣接リスト表現 (adjacency-list representation)したグラフ
edges: List[list] = [
    [0, 1],  # 0 - 1 の辺
    [0, 2],
    [1, 3]
]
dfs(edges)

searching a node '0'
1 is found and enqueued to todo
2 is found and enqueued to todo
searching a node '2'
searching a node '1'
3 is found and enqueued to todo
searching a node '3'

2次元グリッドでのDFS#

縦\(H\)、横\(W\)のグリッドで、各マスを高々1回訪問するなら計算量は\(O(HW)\)

def dfs_grid(grid, start_i, start_j):
    h = len(grid)
    w = len(grid[0])

    visited = [[False] * w for _ in range(h)]

    def _dfs(i, j):
        visited[i][j] = True
        print(i, j)

        # 隣接するマス（上下左右）を全部探索する
        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ni = i + di  # 新しい座標
            nj = j + dj

            # 範囲外ならスキップ
            if not (0 <= ni < h and 0 <= nj < w):
                continue

            # 壁ならスキップ
            if grid[ni][nj] == "#":
                continue

            # 訪問済みならスキップ
            if visited[ni][nj]:
                continue

            _dfs(ni, nj)

    _dfs(start_i, start_j)

grid = [
    "...",
    ".#.",
    "..."
]
# .: 通れるマス
# #: 通れないマス（壁）
dfs_grid(grid, start_i=0, start_j=0)

0 0
1 0
2 0
2 1
2 2
1 2
0 2
0 1

2次元グリッドでのDFS + バックトラックあり#

通常のDFSでは一度探索した経路は再訪問しない（探索を目的とするので）

しかし、様々な経路をたどって最大の利得を得る問題などでは「一旦戻って別の経路を見る」という形で再訪問を許容することもある。その場合はバックトラックを入れる。

例#

目的：

  • 合計スコアが最大になる経路と最大スコアを求める

制約条件：

  • grid[i][j] がそのマスのスコア

  • 開始地点のスコアも加算する

  • 上下左右に移動可能

  • 最大 max_steps 回まで移動可能

  • 同じ経路内では同じマスを再訪問しない

この場合、計算量は最大ステップ数を\(K\)とすると、4方向とステップ数で\(O(4^K)\)ほどになる

def dfs_max_score(grid, start_i, start_j, max_steps):
    h = len(grid)
    w = len(grid[0])

    visited = [[False] * w for _ in range(h)]

    best_score = -10**18
    best_path = []

    def _dfs(i, j, steps, score, path):
        nonlocal best_score, best_path  # 再帰関数外の変数を参照する

        # 現在地点までのスコアで最大値を更新
        if score > best_score:
            best_score = score
            best_path = path[:]

        # これ以上移動できないなら終了
        if steps == max_steps:
            return

        # 上下左右に移動
        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ni = i + di
            nj = j + dj

            # 範囲外ならスキップ
            if not (0 <= ni < h and 0 <= nj < w):
                continue

            # 現在の経路ですでに訪問済みならスキップ
            if visited[ni][nj]:
                continue

            # 次のマスに進む
            visited[ni][nj] = True
            path.append((ni, nj))

            _dfs(
                ni,
                nj,
                steps + 1,
                score + grid[ni][nj],
                path
            )

            # バックトラック
            path.pop()
            visited[ni][nj] = False  # 訪問済みを消す

    # 開始地点
    visited[start_i][start_j] = True
    _dfs(
        start_i,
        start_j,
        steps=0,
        score=grid[start_i][start_j],
        path=[(start_i, start_j)]
    )

    return best_score, best_path

grid = [
    [5, 3, 2],
    [1, 9, 4],
    [7, 2, 8],
]

best_score, best_path = dfs_max_score(
    grid,
    start_i=0,
    start_j=0,
    max_steps=4
)

print(f"{best_score=}")
print(f"{best_path=}")

best_score=29
best_path=[(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)]
Contents