01-BFSのちょっと丁寧な解説

先日Twitterで少し話題になったので書いてみます。データ構造とアルゴリズム Advent Calendar 2018 の8日目の記事でもあります。

「01-BFS」というものをちょっと丁寧に解説します。これは以下のような問題を解くことができるアルゴリズムです。

辺の長さが0または1である有向グラフにおいて、ある1つの始点から全頂点への最短路の長さを効率的な計算時間で求めよ。

f:id:betrue12:20181207211652p:plain

※図のグラフは非循環（DAG）ですが、必ずしもDAGである必要はないです。

この記事では01-BFSの解説の前に「ダイクストラ法」「幅優先探索」をそれぞれ復習し、その流れで01-BFSを解説します。必須ではありませんが、これら2つのコードを書いたことがない人は是非そちらからやってみてください。

ダイクストラ法

多くの人は深さ/幅優先探索→ダイクストラ法の順に学ぶと思いますが、今回は逆の記載順にしています。

ダイクストラ法は、以下の問題を解くことができるアルゴリズムです。

辺の長さが非負である有向グラフにおいて、ある1つの始点から全頂点への最短路の長さを効率的な計算時間で求めよ。

ダイクストラ法においては、全頂点について「それまでに見つかった、始点からの最短距離」を保持します。これを暫定最短距離と表記します。初期値は始点だけ0、それ以外の頂点は無限大（実装上は十分大きい値）です。

アルゴリズムは、まず始点を探索候補に加え、以下を繰り返すことで動作します。

探索候補の中で、暫定最短距離が最も小さい頂点 $v$ を取り出す。
頂点 $v$ から伸びる辺を用いて暫定最短距離を更新できる頂点がある場合、更新してその頂点を探索候補に加える。

この「暫定最短距離が最も小さい頂点を取り出す」という処理を実現するため、多くの場合は優先度付きキュー（＋適切な枝刈り）が用いられます。

ダイクストラ法は何故効率的に、ムダなく動作するのでしょうか？その理由は、端的に言うと二度手間が起こらないからです。

辺の長さが全て非負であるグラフにおいては、経路を進むことで始点からの合計距離が減るということがありません。そのため各ステップにおいて取り出す「暫定最短距離が最も小さい頂点」は、真の最短距離になっていることが保証されています。

f:id:betrue12:20181207212459p:plain

「暫定最短距離が小さいところをどんどん探索していったけど、後で近道が見つかっちゃったから全部探索し直しになる」ということは発生しません。

逆に言うと、長さが負の辺が存在する場合はこういうことが起こり得るので効率的に動作しません。最悪、長さが負の閉路で永遠にループして探索が終わらない可能性もあります。

f:id:betrue12:20181207213201p:plain

各ステップにおいて暫定最短距離が最も小さい頂点を取り出すことで、効率的な探索をすることができる。これがダイクストラ法のキモであり、この記事でも最も重要なポイントです。

幅優先探索による最短路問題

次は幅優先探索です。単なる全探索以外の目的で幅優先探索を用いる問題は、グリッドで表現された迷路などの移動回数を最小化するものが多いです。移動回数の最小化は、移動を長さ1の辺としたときの最短路問題と見なすことが出来ます。

f:id:betrue12:20181207213809p:plain

もちろんこれを優先度付きキューで解くこともできますが、これは「先入れ先出し（FIFO）」の機能を持つキューで実装するほうが効率的です。先ほどと同様に全頂点の暫定最短距離を保持し、まず始点をキューに加え、以下を繰り返します。

キューの先頭から頂点 $v$ を取り出す。
頂点 $v$ から伸びる辺を用いて暫定最短距離を更新できる頂点がある場合、更新してその頂点をキューの末尾に加える。

このアルゴリズムが動作している最中のキューの状態を考えてみます。先頭の頂点を取り出して、その暫定最短距離より距離が1大きい頂点が末尾に追加される…という操作が繰り返されるので、キューの中にある頂点の暫定最短距離は以下のようになっているはずです。

$1, 1, 1, 2, 2$ とか
$3, 3, 4$ とか
$100, 100, 100, 100$ とか

つまり「全てが同じ値である」または「ある値が前側に、それより1大きい値が後ろ側にそれぞれ固まっている」ような状態です。常にこのような状態になるので、先頭から取り出した頂点は常に暫定最短距離が最も小さい頂点になっているわけですね。

つまりキューを使うといっても、暫定最短距離が最も小さい頂点が先頭にある状態を常に保ってさえいればよくて、探索順序がFIFOである必要は全然無いのです。ここが後の説明に繋がります。

ここまでのまとめ

やりたいことはダイクストラ法も幅優先探索も同じで、「辺長が非負で始点が1点固定の最短路問題」を効率的に解くために、暫定最短距離が最も小さい頂点を選んで、そこから伸びる辺で他の頂点の暫定最短距離を更新することを繰り返したいのです。

それを具体的に実現する手続きにおいて、一般的な条件だと優先度付きキューが使えるし、辺長が全て1の場合はキューが使える、ということですね。

ここを再確認した後で、いよいよ01-BFSの説明です。

01-BFS

ここまでの内容が理解できていれば、01-BFSは自然に理解することができます。

先ほどは辺長が全て1の最短路問題を考えました。01-BFSはこれを少しだけ難しくした、辺の長さが0または1の最短路問題を解く方法です。

f:id:betrue12:20181207211652p:plain

キーポイントは辺長が全て1の場合と同じく、探索候補の順番を暫定最短距離で見て $3, 3, 4$ のような「全てが同じ値である」または「ある値が前側に、それより1大きい値が後ろ側にそれぞれ固まっている」という状態に保つことです。始点からの暫定最短距離が3である先頭の頂点を取り出して遷移先をチェックしたとき、その経路での始点から遷移先までの距離は辺長0ならば3、辺長1ならば4になります。このとき

距離3ならば探索候補の先頭に追加することで、候補の並びは $3, 3, 4$ になる。
距離4ならば探索候補の末尾に追加することで、候補の並びは $3, 4, 4$ になる。

とすることで、「全てが同じ値である」または「ある値が前側に、それより1大きい値が後ろ側にそれぞれ固まっている」という状態を常に保つことが出来ます。

先ほど「FIFOである必要はない」と書いたのはこういうことで、このように先頭にデータを割り込ませても良いのか少し不安になりますが、これで正しく機能します。

あとはこの操作を効率的に実現するデータ構造があればアルゴリズムを実装することができて、多くの場合両端キューが用いられます。両端キューは先頭と末尾の両方に対して要素の追加と取り出しを $O(1)$ で処理できるデータ構造です。

01-BFSではまず始点を両端キューに加え、以下を繰り返します。

両端キューの先頭から頂点 $v$ を取り出す。
頂点から伸びる辺を用いて暫定最短距離を更新できる頂点がある場合、更新してその頂点を
- 0の辺を用いた場合は両端キューの先頭に加える。
- 1の辺を用いた場合は両端キューの末尾に加える。

こう書いてしまうと理屈はとてもシンプルです。ダイクストラ法と幅優先探索をしっかり理解することが、01-BFSを理解する一番の近道です。

計算量のはなし

頂点数を $V$ 、辺数を $E$ とします。よく使われる実装ではこのようになります。

ダイクストラ法（優先度付きキュー利用）： $O(V + E\log V)$
幅優先探索（キュー使用）： $O(V + E)$
01-BFS（両端キュー使用）： $O(V + E)$

これまで見てきたようにどれもやっていることは大体同じなので、探索候補を格納するデータ構造の操作にどれだけ時間が掛かるかという点で差が出ています。

※ダイクストラ法の計算量は（優先度付きキュー利用を前提としても）細かい実装や資料によって書かれ方が色々違っていることがあります。グラフが単純かつ始点から全頂点に到達可能であると仮定すると $V-1 \le E \le V(V-1)$ が成り立つので、だいたいの実装は式変形すると上記の評価になると思います。

01-BFSを使う問題

01-BFSが比較的素直に使える問題を紹介します。私もあまりたくさんは知りません。

※（2018年12月時点で）AtCoder過去問を新しい方から埋めていった場合、多くの人が最初に「01-BFS」という単語を目にする問題はコレだと思いますが…これは01-BFSに帰着させるまでの考察が問題のほぼ全てなので、リストには含めていません。

問題文を読んでいただければわかるように、

ノーコストの手段で移動する
何らかのコストや回数制限のある手段で移動する

の2通りの移動方法が与えられているような問題は、01-BFSに帰着できることがあります。

ただ…これらの問題は全て、高速な言語であればダイクストラ法でも十分間に合います。もしかしたらスクリプト言語を使っている人のほうが、01-BFSを必要とする機会が多いかもしれません。

実装例

隣接リストでグラフを管理しているときの01-BFSの実装例です。入力などを受け取るところは省略しています。

C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    // 頂点数N、始点の頂点番号s
    int N, s;
    // 隣接リスト。
    // edges[i]の要素に(j, c)が含まれる時、iからjにコストcの辺が存在
    vector<vector<pair<int, int>>> edges(N);

    vector<int> dist(N, 1e9);
    dist[s] = 0;
    deque<int> que;
    que.push_back(s);

    while(que.size()){
        int i = que.front(); que.pop_front();
        for(auto [j, c] : edges[i]){
            int d = dist[i] + c;
            if(d < dist[j]){
                dist[j] = d;
                if(c){
                    que.push_back(j);
                }else{
                    que.push_front(j);
                }
            }
        }
    }
}

Python

from collections import deque

# 頂点数N、始点の頂点番号s
N, s = map(int, input().split())
# 隣接リスト。
# edges[i]の要素に(j, c)が含まれる時、iからjにコストcの辺が存在
edges = [[] for i in range(N)]

dist = [10**9]*N
dist[s] = 0
que = deque()
que.append(s)

while len(que) > 0:
    i = que.popleft()
    for j, c in edges[i]:
        d = dist[i] + c
        if d < dist[j]:
            dist[j] = d
            if c == 1:
                que.append(j)
            else:
                que.appendleft(j)