LoginSignup
34
49

More than 1 year has passed since last update.

@keisuke-ota(太田 圭祐)

【Python】クラスで実装する幅優先探索（BFS）と深さ優先探索（DFS）

Last updated at Posted at 2021-04-29

概要

本稿では競技プログラミング：AtCoder の過去問を用いて、木構造やグラフ構造のデータに対する全探索アルゴリズム：幅優先探索（Breadth First Search：BFS） と 深さ優先探索（Depth First Search： DFS） の実装例を紹介する。BFS や DFS は特定のノードから隣接ノードを辿って行われる探索アルゴリズムの一種である。以下の実装例では隣接リストや探索済フラグをもつ Node オブジェクトを使用した。

Nodeオブジェクト
class Node:
    """

    ノード情報の管理

    Attributes:
        index (int): ノード番号
        nears (list): 隣接リスト（隣接するノード番号を格納）
        arrival (bool): 探索済フラグ（到達済の場合Trueが返される）
    """

    def __init__(self, index):
        self.index = index
        self.nears = []
        self.arrival = False

    def __repr__(self):
        return f"(index:{self.index}, nears:{self.nears}, arrival:{self.arrival})"

BFSおよびDFSの実装フロー

  • 1.Node インスタンスを生成し適当なオブジェクトに格納する。
  • 2.Node インスタンスに隣接リストを付与する
  • 3.BFS の起点となるノード、すなわち root を取得する
  • 4.BFS を実施する
    • a. 探索ノードの格納先である queue に探索開始ノードを追加する
    • b. 探索開始ノードの到達済フラグを立てる
    • c. queue がなくなるか、目的のノードに到達するまで以下の処理を繰り返す
      • 1). queue からノードを 1 つ取り出す。このとき pop() で取り出すと DFS が実施され、popleft() で取り出すと BFS が実施される
      • 2). 取り出したノードの隣接リストを格納する
      • 3). 隣接リストからノードを 1 つずつ取り出し、探索済みかどうかを arrival で確認する。
      • 4). 未探索のノードは queue に append() で追加し、探索済フラグを立てる。

DFS の場合、探索ノードを格納するデータ構造は queue ではなく stack となる。

実装例（1） ABC168 D 問題（最短経路を求める問題）

問題概要

$N$ 個の部屋を $M$ 個の通路が結ぶ。部屋と通路には 1 から順に番号が与えられている。$i$ 番目の通路は部屋 $A_i$ と部屋 $B_i$ を双方向に繋いでいる。
部屋1から通路を通って部屋2〜部屋Nの全てに到達できる場合Yesを出力し、そうでなければ No と出力せよ。またYesを出力する場合は、部屋2〜部屋Nのそれぞれから部屋1へ最短で向かう際に進む最初の部屋番号を答えよ。

標準入力で各通路が結ぶ部屋番号が与えられる。詳細は問題文を参考にしよう。

入力例
4 4
1 2
2 3
3 4
4 2
入力例に対する正解出力
Yes
1 
2
2
  • Node 2 から node 1 への最短経路で最初に進む部屋は node 1 なので出力は 1
  • Node 3 から node 1 への最短経路で最初に進む部屋は node 2 なので出力は 2
  • Node 4 から node 1 への最短経路で最初に進む部屋は node 2 なので出力は 2

実装例

部屋の情報をNodeインスタンスで持ち、Node 1 からの BFS を実施する。探索フラグとして親ノードの番号を持っておくとよい。親ノードが-1の場合、そのノードは未探索である。

実装例
from collections import deque

class Node:
    """

    ノードの情報を管理

    Attributes:
        index (int): 自分のノード番号
        nears (list): 隣接リスト
        parent (int): 親のノード番号
    """

    def __init__(self, index):
        self.index = index
        self.nears = []
        self.parent = -1

    def __repr__(self):
        return f"(index:{self.index}, nears:{self.nears}, parent:{self.parent})"


# 入力読込
N, M = map(int, input().split())
# Nodeインスタンスを作成しnodesに格納
nodes = [Node(i) for i in range(N + 1)]

# 隣接リストを付与
for _ in range(M):
    s, g = map(int, input().split())
    nodes[s].nears.append(g)
    nodes[g].nears.append(s)

# 探索キューを作成
queue = deque([])

# ノード1からBFS開始
queue.append(nodes[1])

# ノード1の親ノードを便宜上0とする
nodes[1].parent = 0

# BFS 開始
while queue:
    # キューから探索先を取り出す
    node = queue.popleft()
    # print(node)←現在地を出力
    # 現在地の隣接リストを取得
    nears = node.nears
    for near in nears:
        # 親ノードが-1なら未探索
        if nodes[near].parent == -1:
            # 未探索ノードをキューに追加
            queue.append(nodes[near])
            # 親ノードを追加
            nodes[near].parent = node.index

# 親ノードを格納
ans = [nodes[i].parent for i in range(2, N + 1)]
# -1が含まれていたらノード1に辿り着けないノードが存在する
if -1 in ans:
    print("No")
else:
    print("Yes")
    for a in ans:
        print(a)

実装例（2） ATC 001 A 問題

問題概要

高さ $H$ 、幅 $W$ の区画で通路 . を通ってスタート s からゴール g までたどり着けるか判定せよ。ただし # は塀のため通過できない。

入力例
11 33
s................................
#.###############################
.................#g..............
#########.##################.####
.............#.......#...........
###.###############.#######.#####
.........#.......................
#####.########.##########.#######
....................#............
.#############.###########.######
.......#...........#.............
入力例に対する正解出力
Yes

実装例

通路を node とする。node の座標を row と col で表す。

実装例
class Node:
    """

    区画の情報を管理

    Attributes:
        row (int): 区画の行番号（0-indexed）
        col (int): 区画の列番号（0-indexed）
        nears (list): 隣接リスト
        arrival (bool): 探索フラグ
    """

    def __init__(self, row, col):
        self.row = row
        self.col = col
        self.nears = []
        self.arrival = False

    def __repr__(self):
        return f"(row:{self.row}, col:{self.col}, arrival:{self.arrival})"


H, W = map(int, input().split())
# 街の情報を取得
locs = [input() for _ in range(H)]

# 探索クエリをスタックで取得
stack = []

# Nodeインスタンスを作成
nodes = [[Node(i, j) for j in range(W)] for i in range(H)]

# 東西南北の方向を取得
adjacents = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# i行目j列目の街の情報を調査
for i in range(H):
    for j in range(W):
        # 隣接区画が塀でなければ隣接リストに追加する
        for dx, dy in adjacents:
            nx, ny = i + dx, j + dy
            if (0 <= nx < H) & (0 <= ny < W):
                if locs[nx][ny] != "#":
                    nodes[i][j].nears.append([nx, ny])
        # 探索開始ノードをスタックに追加
        if locs[i][j] == "s":
            stack.append(nodes[i][j])
            nodes[i][j].arrival = True

# DFS
while stack:
    # stack から探索先をひとつ取り出す
    node = stack.pop()
    # print(node) ←現在地取得
    # 現在地がゴールなら探索取得
    if locs[node.row][node.col] == "g":
        print("Yes")
        exit()
    # 現在地の隣接リストを取得
    nears = node.nears
    for r, c in nears:
        # 隣接ノードが未探索ならスタックに追加
        if nodes[r][c].arrival == False:
            nodes[r][c].arrival = True
            stack.append(nodes[r][c])

# 最後までゴールに辿り着けなかった場合はNoを出力
print("No")

実装例（3） ARC 031 B 問題

問題概要

10 x 10 のマス目において o を陸とし、 x を海とする。必要であれば x を 1 マスだけ埋め立てて陸地が全て繋がるかどうかを判定せよ。最初から陸続きの場合か、埋め立てて陸続きになる場合は YES を出力し、そうでない場合はNOを出力せよ。

入力例
xxxxxxxxxx
xoooooooxx
xxoooooxxx
xxxoooxxxx
xxxxoxxxxx
xxxxxxxxxx
xxxxoxxxxx
xxxoooxxxx
xxoooooxxx
xxxxxxxxxx
入力例に対する正解出力
YES

実装例

最初に陸地の総面積を取得する。次に10×10のマス目のそれぞれについて、そのマスを埋め立てたときに陸続きとなるマス目の面積をDFSで求める。陸続きの面積が陸地の総面積と等しくなる埋め立て場所が1つでもあればYESを取得する。

実装例
class Node:
    """

    区画の情報を管理

    Attributes:
        row (int): 区画の行番号（0-indexed）
        col (int): 区画の列番号（0-indexed）
        nears (list): 隣接リスト
        arrival (bool): 探索済フラグ
    """

    def __init__(self, row, col):
        self.row = row
        self.col = col
        self.nears = []
        self.arrival = False

    def __repr__(self):
        return f"(row:{self.row}, col:{self.col}, arrival:{self.arrival})"

H, W = 10, 10
# 島の情報を取得
locs = [input() for _ in range(H)]
# 陸地面積を取得
lands_area = sum([loc.count("o") for loc in locs])

# 探索クエリをスタックで取得
stack = []

# Nodeインスタンスを作成
nodes = [[Node(i, j) for j in range(W)] for i in range(H)]

adjacents = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# i行目j列目の島の情報を調査
for i in range(H):
    for j in range(W):
        # 隣接区画が陸であれば隣接リストに追加する
        for dx, dy in adjacents:
            nx, ny = i + dx, j + dy
            if (0 <= nx < H) & (0 <= ny < W):
                if locs[nx][ny] == "o":
                    nodes[i][j].nears.append([nx, ny])

ans = "NO"

# DFS
for i in range(H):
    for j in range(W):
        # i行目j列目を埋め立てたとき探索可能な陸地の面積(area)を求める
        stack = [nodes[i][j]]
        nodes[i][j].arrival = True
        # 埋立地は元々陸地ではなかったため-1から陸地を数える
        area = -1
        while stack:
            # stack から探索先をひとつ取り出す
            node = stack.pop()
            area += 1
            # print(node) ←現在地取得
            # 現在地の隣接リストを取得
            nears = node.nears
            for r, c in nears:
                # 隣接ノードが未探索ならスタックに追加
                if nodes[r][c].arrival == False:
                    nodes[r][c].arrival = True
                    stack.append(nodes[r][c])

        # 探索可能範囲が陸地面積と等しくなる埋め立て方があればYes
        if area == lands_area:
            ans = "YES"

        # 探索フラグを初期化する
        for r in range(H):
            for c in range(W):
                nodes[r][c].arrival = False

print(ans)

実装例（4）ABC 088 D 問題（最短経路長を求める問題）

問題概要

縦 H マス横 W マスにマス目が広がっている。通路を .、壁を # とするとき、通路だけを通って左上のマスから右下のマスを結ぶ最短経路を調べ、最短経路と壁を除く通路の面積を求めよ。

入力例
3 3
..#
#..
...
入力例に対する正解出力
2

実装例

探索開始ノードからの最短経路長をdepthに格納する。

実装例
from collections import deque

class Node:
    """

    区画の情報を管理

    Attributes:
        row (int): 区画の行番号（0-indexed）
        col (int): 区画の列番号（0-indexed）
        nears (list): 隣接リスト
        depth (bool): 根からの深さ
    """

    def __init__(self, row, col):
        self.row = row
        self.col = col
        self.nears = []
        self.depth = -1

    def __repr__(self):
        return f"(row:{self.row}, col:{self.col}, depth:{self.depth})"


H, W = map(int, input().split())
# マスの情報を取得
locs = [input() for _ in range(H)]
# 黒マスの総数を取得
blacks = sum([loc.count("#") for loc in locs])

# 探索クエリをスタックで取得
queue = deque([])

# Nodeインスタンスを作成
nodes = [[Node(i, j) for j in range(W)] for i in range(H)]

# 東西南北の方向を取得
adjacents = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# i行目j列目のマスの情報を調査
for i in range(H):
    for j in range(W):
        # 隣接区画が塀でなければ隣接リストに追加する
        for dx, dy in adjacents:
            nx, ny = i + dx, j + dy
            if (0 <= nx < H) & (0 <= ny < W):
                if locs[nx][ny] != "#":
                    nodes[i][j].nears.append([nx, ny])

# 探索開始ノード(0,0)をスタックに追加
if locs[0][0] == ".":
    queue.append(nodes[0][0])
    nodes[0][0].depth = 1

# BFS
while queue:
    # queue から探索先をひとつ取り出す
    node = queue.popleft()
    # print(node)  # ←現在地取得
    # 現在地の隣接リストを取得
    nears = node.nears
    for r, c in nears:
        # 隣接ノードが未探索ならスタックに追加
        if nodes[r][c].depth == -1:
            nodes[r][c].depth = node.depth + 1
            queue.append(nodes[r][c])

# ノード(H-1,W-1)に到達できなければ-1
shortest_path_len = nodes[H - 1][W - 1].depth

if shortest_path_len == -1:
    print(-1)
else:
    print(H * W - blacks - nodes[H - 1][W - 1].depth)

実装例（5）ABC 204 C 問題

問題概要

$N$ 個の都市を $M$ 個の道路が結ぶ。都市と道路には 1 から順に番号が与えられている。$i$ 番目の通路は都市 $A_i$ から都市 $B_i$ へ有方向で繋いでいる。移動可能な都市の組の総数を答えよ。

実装例

Node 1 〜 N をそれぞれ開始地点とする DFS または BFS を実施して、スタート地点とゴール地点のペアを1つずつ数える。

実装例
class Node:
    """

    ノードの情報を管理

    Attributes:
        index (int): 自分のノード番号
        nears (list): 隣接リスト
        arrival (bool): 探索済フラグ
    """

    def __init__(self, index):
        self.index = index
        self.nears = []
        self.arrival = False

    def __repr__(self):
        return f"(index:{self.index}, nears:{self.nears}, arrival:{self.arrival})"


# 入力読込
N, M = map(int, input().split())
# Nodeインスタンスを作成しnodesに格納
nodes = [Node(i) for i in range(N + 1)]

# 隣接リストを付与
for _ in range(M):
    s, g = map(int, input().split())
    nodes[s].nears.append(g)

# スタートとゴールの組:
ans = N

for i in range(1, N + 1):

    # 探索スタックを作成
    stack = [nodes[i]]

    # ノードiからDFS開始
    stack.append(nodes[i])

    # ノードiの親ノードを便宜上0とする
    nodes[i].arrival = True

    # DFS
    while stack:
        # スタックから探索先を取り出す
        node = stack.pop()
        # print(node)←現在地を出力
        # 現在地の隣接リストを取得
        nears = node.nears
        for near in nears:
            # 親ノードが-1なら未探索
            if nodes[near].arrival == False:
                # 未探索ノードをスタックに追加
                stack.append(nodes[near])
                # 探索フラグ更新
                nodes[near].arrival = True
                # ノードiからnearは到達可能
                ans += 1

    for i in range(1, N + 1):
        nodes[i].arrival = False

print(ans)
34
49
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
34
49