【詳解Python】幅優先探索BFS/深さ優先探索DFSがわかる解説

用語

ここからの解説は略語を作って話すことが多いので先に単語を紹介しておきます

BFS – 幅優先探索(Breadth First Search)

DFS – 深さ優先探索(Depth First Search)、どっちがどっちかわからなくなったら深い(Deep)のDだから「DFS」が深さ優先探索と覚える

結論：BFS/DFSの違いは何か？

探索はとは、グラフで今いる場所から行ける場所を順番に辿っていくことです。幅優先探索と深さ優先探索はたどる順番が違います

幅優先探索(BFS)は、今いる場所から近いノードから順にたどる

深さ優先探索(DFS)は、経路で行くことができる一番遠い場所までたどる

ここに家族を表したグラフがあります。このグラフの始点は自分とします。

幅優先探索(BFS)では、自分から近いノード「父->母」からたどって、次に「父祖父->父祖母->母祖父->母祖母」とたどります

深さ優先探索(DFS)では、父からたどるとすると、その父方家系の先祖までたどっていきます。なので「父->父祖父」からたどり、今いる先祖の遠い場所までいったので父にもどって探索を開始すると「->父祖母」となります。

父方の家系を全て探索しきってからようやく母方の家系を調べます。なので「->母->母祖父->母祖母」とたどります

再帰関数

BFSは再帰関数かスタックというもので実装することになるので、今回は再帰関数のことを説明します

再帰関数とは、関数のなかで自分の関数を呼ぶような関数のこと。実装例で示します

フィボナッチ数

1. 最初の二つを1として始める。
2. それ以降は、直前の二つの和を求める

具体的には、1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...となっていく

def fibonacci(n):
    # ここが終了条件になる
    if n == 1 or n == 2:
        return 1
        
    # ここで自分の関数を呼び出す
    return fibonacci(n - 1) + fibonacci(n - 2) 

この関数について考えてみましょう。

まずfibonacci(3)の時は、その中でfibonacci(2)とfibonacci(1)を呼び出す。n = 1, 2の時は1を返すので最終的にfibonacci(2)+fibonacci(1)=2を返す

fibonacci(4)のとき、fibonacci(3)とfibonacci(2)の答えを使って2+1の3が返される

再帰関数は、一度プログラムを見ただけでは流れが理解しにくいものの欠点があるものの実際に数値を入れて考えると簡潔にコードが書けることがあります

迷路での深さ優先探索の実装

入力

5 5
S####
....#
.##.#
.##.#
###..

これは、「#」が壁、「.」が通路、Sがスタート、迷路で、最初の数字が迷路の高さと幅を与えているものとします。

どんなが迷路与えたれてもゴールに辿りつけるようにプログラムを組んでいきます。

考え方

「今いる場所から上下左右が通路なら進む」をゴールまで繰り返す

実装

h, w = map(int, input().split())　# 高さと幅
maze = [list(input()) for i in range(h)]　# 迷路の文字列を一文字づつ取得する

def is_in_field(x, y):
    if 0 <= x < h and 0 <= y < w:　# 高さを幅の中ならフィールド内
        return True
    else:
        return False

def dfs(x, y):
    print(x, y) # 場所(x, y)を表示する

    for dx, dy in [(1, 0), (-1, 0), (0 , 1), (0 , -1)]:
        # dx, dy = (1, 0)が回されたとき、
        # x1, y1 = x + 1, y となるように
        # それぞれ上下左右を回すことができる
        x1 = x + dx
        y1 = y + dy
        
        if not is_in_field(x1, y1): # 場所(x1, y1)が迷路のフィールドの中でなかったら
            continue # 次のループまでとばす

        if maze[x1][y1] == '.': # 迷路が進めるのなら
            maze[x1][y1] = '*' # 通過済みを*で示す
            dfs(x1, y1) # 右でまた探索する

dfs(0, 0)
  

迷路の動きの以下のようになります

1
S####
...##
.##.#
.##.#
....#

2
S####
*..##
.##.#
.##.#
....#

3
S####
*..##
*##.#
.##.#
....#

4
S####
*..##
*##.#
*##.#
....#

5
S####
*..##
*##.#
*##.#
*...#

6
S####
*..##
*##.#
*##.#
**..#

7
S####
*..##
*##.#
*##.#
***.#

8
S####
*..##
*##.#
*##.#
****#

9
S####
*..##
*##.#
*##*#
****#

10
S####
*..##
*##*#
*##*#
****#

11
S####
**.##
*##*#
*##*#
****#

12
S####
***##
*##*#
*##*#
****#

こうして、行ける場所を全て探索することができました

次の記事では、グラフでの探索についての解説をしていきます