BFS(幅優先探索)とぶつかり稽古

AtCoderをやっていく上で必ずぶつかるのがこのBFS。グラフ探索の手法である。

ここでは原理の復習から実装までを行う。

なおこの記事を書く上で以下の記事をものすごく参考にさせてもらった。ほんま感謝やでえ。

qiita.com

BFSの動作

BFSは重みなしグラフ(もしくは各辺の重みが等しいグラフ)における、探索の始点となる頂点から各頂点への最短経路を求めることのできるアルゴリズムである。

BFSのアイデアは非常に単純で、まず始点の近傍を探索、次にその近傍を探索,さらにそのまた近傍を探索...と続け、近傍から到達可能な全ての頂点が探索済みになった時点で終了するというものだ。

アルゴリズムの概要は以下の通り。

まず始点をキュー*1に格納する。キューに格納されているというのは、その点が訪問予定(発見済みだが隣接点を未探索)の状態であることを意味する。

キューから先頭の要素 $v$ を取り出す。

$v$ の隣接点の中で未発見であった点に対し、始点からの距離を定め、その点をキューの末尾に追加する。

2,3を繰り返し、キューが空になった段階で終了。

ぼくを含めたみんなはこれを見ただけじゃどういうことか分からないと思うので以下でイメージの図(おんなじ意味!)を与える。

オレンジが「訪問予定」、赤が「訪問済み」、各点左上に書かれた数字がその点までの最短経路長である。10枚目の画像でキューが空となったのでアルゴリズムは終了する。

(追記)
10枚目の頂点6の上に3を書き忘れてました。ごめんな。

BFSが最短経路長を正しく与える証明

BFSの正当性は自明では無いためここで証明を与える。

なお、以下ではグラフが有向グラフである場合のBFSの正当性の証明を与えるが、無向グラフは各辺を二本の有向辺と捉えることで有向グラフとして表現できるため、同時に無向グラフの場合でもBFSが正当であることが証明される。

では、まず証明に用いる補題の証明から。

Lemma

$G=(V,E)$ を有向グラフとし、 $v\in V$ とする。また、 $u\in V$ に対して $P_u$ を $v$ から $u$ への最短路とする。
この時、 $\forall w \in V(P_u)\,$ (経路 $P_u$ 上に含まれる頂点集合)に対して $P_u$ 上の $w$ までの経路は $v$ から $w$ への最短路である。

(証明)
ある $u\in V$ に対して $P_u$ 上の $w$ までの経路が $v$ から $w$ までの最短路になっていないような頂点 $w\in V$ の存在を仮定する。

すると、 $P_w$ と $P_u$ 上の $w$ 以降の経路を繋いだ経路 $P'_u$ は $P_u$ より短い経路となり $P_u$ が最短路であることに矛盾する。

(証明終わり)

続いて本題の証明。

Theorem

頂点数 $n$ 、辺数 $m$ の有向グラフ $G=(V,E)$ が与えられた時、頂点 $s\in V$ を始点とする幅優先探索を実行し終わった段階で、 $d(v)\,$ (アルゴリズム中で求めた各点への距離)が始点から各頂点 $v\in V$ への最短路長となる。

(証明)
$v\in V$ に対して、 $l_v$ を $s$ から $v$ への最短路長とする。 $s$ から $v$ への経路がない場合は $l_v=\infty$ とする。このとき、任意の $v\in V$ に対して $l_v=d(v)$ となることを示す。まず、任意の $k\in \mathbb{N}$ と任意の $v\in V$ に対して $l_v=k\Leftrightarrow d(v)=k$ となることを示す。

k=0のとき、 $l_v=0$ となる頂点は $s$ のみである。このとき $d(s)=0$ である。また、 $d(v)=0$ となる頂点も $s$ のみであり、 $l_s=0$ である。したがって $k=0$ のとき成立する。

$k\leq n$ のときに主張が成立すると仮定する。まず $l_w=n+1 \Rightarrow d(w)=n+1$ を示す。

$l_w=n+1$ となる頂点 $w\in V$ を固定する。 $d(w) < n+1$ と仮定すると、帰納法の仮定より $d(w)=l_w < n+1$ となり矛盾する。したがってこのとき $d(w)\geq n+1$ である。

$P_w$ を $s$ から $w$ への最短路とする。Lemmaより $P_w$ の $w$ の1つ前の頂点を $v$ とすると、 $P_v := (P_w$ から辺 $(v,w)$ と頂点 $w$ を取り除いた経路 $)$ は $s$ から $v$ への最短路になっていて $l_v=n$ が成り立つ。
すると仮定より、 $d(v)=n$ となる。よって、任意の $w$ への最短路について $w$ の1つ前の頂点を $v$ とすると、 $d(v)=n$ となる。

以上をまとめると、 $l_w=n+1$ という仮定のもと $w$ に入る頂点 $v$ の中で $d(v)=n$ となるものが存在する。
同時に、 $w$ に入る頂点 $x$ で $d(x) < n$ となるものは存在しない(そのような $x$ が存在する場合、帰納法の過程より $l_x < n$ となるがそのとき明らかに $l_w < n+1$ となってしまうので矛盾)。
BFSのアルゴリズムでは $d(v)$ の値の昇順に探索が行われるので $d(w)$ の値は $d(v) = n$ となる頂点 $v$ によって書き換えられ、 $d(w)=n+1$ となる。

次に $d(w)=n+1 \Rightarrow l_w=n+1$ を示す。

$d(w)=n+1$ となる頂点 $w\in V$ を固定する。 $l_w < n+1$ と仮定すると上と同様の理由から矛盾。したがって $l_w \geq n+1$ である。

$d(w)$ の値を書き換えた頂点を $v$ とすると、 $d(v)=n$ となる。すると帰納法の仮定より $l_v=n$ である。
$P_v$ を $s$ から $v$ までの最短路とし、 $P_w$ を $P_v$ に辺 $(v,w)$ と頂点 $w$ を付け加えた経路とすると、 $P_w$ の長さは $n+1$ である。 $l_w \geq n+1$ であったので $P_w$ は $s$ から $v$ への最短路となっている。したがってこのとき $l_w=n+1$ となる。

よって、任意の $k\in \mathbb{N}$ と任意の $v\in V$ に対して $l_v=k \Leftrightarrow d(v)=k$ となることが示された。

また、上の証明より $l_v$ の有限性と $d(v)$ の有限性も同値であることがわかる。したがって $l_v=\infty \Leftrightarrow d(v)=\infty\,(d(v)=\infty:v$ には到達不可能 $)$ となる。これらを合わせて、任意の頂点 $v\in V$ に対して $l_v=d(v)$ となることが示された。

(証明終わり)

まあ証明なんて別にどうでも良い。次に実装を行っていこう。

BFSの実装

以下のコードでBFSが実装できる。なお入力は以下の形式を想定している。

$\begin{align*} &N\quad M\\ &a_0\quad b_0\\ &a_1\quad b_1\\ &\cdots \\ &a_{M-1}\quad b_{M-1} \\ \end{align*}$

$N$ はグラフの頂点数、 $M$ はグラフの辺数、各辺 $i=0,1,\ldots ,M-1$ は頂点 $a_i$ と $b_i$ をつないでいることを表している。

N,M=map(int,input().split())
G=[[] for i in range(N)] #グラフを隣接リストで表現する

for i in range(M):
    a,b=map(int,input().split())
    G[a].append(b) #aからbに入る有向辺が存在
    G[b].append(a) #bからaに入る有向辺が存在

from collections import deque

def BFS(u): #点uから各点への最短距離のリストを返す関数
    queue=deque([u])
    dist=[float('inf')] * N #uからの距離の初期化
    dist[u]=0 #始点との距離は0
    while queue:
        v=queue.popleft()
        for i in G[v]:
            if dist[i] == float('inf'):
                dist[i]=dist[v]+1
                queue.append(i)
    return dist

dist=BFS(0) #点0から各頂点への最短路
print(dist) #最短路のリストが出力される。到達不可能点の場合、最短路はinfとなる。

コード中で出てきた隣接リスト表現とは、各頂点 $v$ に対し、 $v$ から出ている辺のリスト $\mathrm{Adj}_v$ (または接続している辺のリスト)を保持するというグラフの格納方法である。

またdequeとは、pythonの標準ライブラリcollectionsモジュールの型の一つでありデータをキューとして扱うときに用いる。様々なメソッドがあり、append()でキューの末尾に追加、popleft()で先頭要素の取得が可能である。

以上が最も基本的なBFSの実装であった。よくよく見れば何も難しい話はない。
名前が某K-POPグループに似ているからと言って、恐るるに足りない。

迷路問題でBFS

実際にAtCoderをやっているとBFSを用いる場面はたくさん出てくるが、その多くは上で見たようなグラフの問題ではなく、"迷路問題"であるように感じる(迷路問題が正しい呼称かは知らないが、とりあえず以下ではそう呼ぶ)。

具体的に以下の問題を考える。

迷路問題1

大きさが $N\times M$ の迷路が与えられる。迷路は通路と壁からできており、1ターンに隣接する上下左右4マスの通路へ移動することができる。スタートからゴールまで移動するのに必要な最小のターン数を求めよ。

これに対しては以下のようにBFSを行うことができる。

from collections import deque

def debug_print(maze): #mazeをきれいに表示するだけの関数(無くても良い)
    for x in maze:
        for y in x:
            print(y,end=" ")
        print("\n")

def clear_maze(Sx, Sy, Gx, Gy, maze): #(Sx,Sy):スタートの座標、(Gx,Gy):ゴールの座標

    debug_print(maze)

    INF = float("inf")

    field_x_length = len(maze) #行数
    field_y_length = len(maze[0]) #列数
    dist = [[INF for i in range(field_x_length)] for j in range(field_y_length)] #距離の初期化
 
    def bfs():
        queue = deque([(Sx,Sy)]) #訪問予定点の座標をキューに追加していく

        dist[Sx][Sy] = 0

        while queue: #queueに要素が入っている限り周り続ける
            x, y = queue.popleft()

            if x == Gx and y == Gy: #ゴール到着
                break

            for i in range(0, 4): #4方向で動ける方向を探す
                nx = x + [1, 0, -1, 0][i] 
                ny = y + [0, 1, 0, -1][i] #i=0:下、i=1:右、i=2:上、i=3:左 へ1マス移動

                if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[nx][ny] != '#' and dist[nx][ny] == INF): #動いた先が未到達点で壁じゃなかったら
                    queue.append([nx,ny])
                    dist[nx][ny] = dist[x][y] + 1

        return dist[Gx][Gy]

    return bfs()


maze = [
    ['#', 'S', '#', '#', '#', '#', '#', '#', '.', '#'],
    ['.', '.', '.', '.', '.', '.', '#', '.', '.', '#'],
    ['.', '#', '.', '#', '#', '.', '#', '#', '.', '#'],
    ['.', '#', '.', '.', '.', '.', '.', '.', '.', '.'],
    ['#', '#', '.', '#', '#', '.', '#', '#', '#', '#'],
    ['.', '.', '.', '.', '#', '.', '.', '.', '.', '#'],
    ['.', '#', '#', '#', '#', '#', '#', '#', '.', '#'],
    ['.', '.', '.', '.', '#', '.', '.', '.', '.', '.'],
    ['.', '#', '#', '#', '#', '.', '#', '#', '#', '.'],
    ['.', '.', '.', '.', '#', '.', '.', '.', 'G', '#'],
    ]

Sx, Sy = 0, 1 # スタート地点の座標
Gx, Gy = 9, 8 # ゴール地点の座標
print (clear_maze(Sx, Sy, Gx, Gy, maze))

これに対する出力は以下の通り。

# S # # # # # # . # 
. . . . . . # . . # 
. # . # # . # # . # 
. # . . . . . . . . 
# # . # # . # # # # 
. . . . # . . . . # 
. # # # # # # # . # 
. . . . # . . . . . 
. # # # # . # # # . 
. . . . # . . . G # 
22

ゴールまでのステップ数が正しく出力されている様子がわかる。

迷路はマス同士が辺で結ばれているグラフであると解釈することができる。
その解釈にのっとると、あるマスの上下左右の４マスを見ることでグラフで言うところのその点から出ていく辺全てを確認したことになる。

よって、グラフと同じようにBFSを実装することが可能なのだ。

せっかくなので、最新のABC176にて出題された迷路問題も扱ってみよう。

迷路問題2

縦 $H$ マス、横 $W$ マスの $H\times W$ マスからなる迷路があります。