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

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

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

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

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

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

ダイクストラ法

※今回はいわゆる「O(V2)$O(V^2)$ のダイクストラ法」は考慮外とします。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ある値が前側に、それより1大きい値が後ろ側に、それぞれ0個以上固まっているような状態です。常にこのような状態になるので、先頭から取り出した頂点は常に暫定最短距離が最も小さい頂点になっているわけですね。便宜上、以降の説明でこれを「理想的な状態」と呼ぶことにします。

つまりキューを使うといっても、探索候補の順番を理想的な状態に保ってさえいればよくて、探索順序がFIFOである必要は全然無いのです。ここが後の説明に繋がります。

ここまでのまとめ

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

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

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

01-BFS

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

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

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

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

とすることで、理想的な状態を保つことが出来ます。

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

あとはこの操作を効率的に実現するデータ構造があればアルゴリズムを実装することができて、多くの場合両端キューが用いられます。まず始点を両端キューに加え、以下を繰り返します。

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

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

計算量のはなし

頂点数を V$V$ 、辺数を E$E$ とします。

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

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

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

01-BFSを使う問題

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

• ARC005 C - 器物損壊！高橋君
• ARC061 E - すぬけ君の地下鉄旅行
• Codeforces Round #516 Labyrinth

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

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

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

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

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

実装例

「器物損壊！高橋君」の実装例です。多めにコメントを付けています。

Submission #3732686 - AtCoder Regular Contest 005

余談：BFSって？

一般に幅優先探索をBFSと略すことが多いですが、この記事では幅優先探索の意味でBFSという略語を使わないようにしました。

01-BFSは「辺コスト1の最短路問題を幅優先探索で解く方法の拡張」ではありますが、これが幅優先（Breadth-First）なのかと言われるとかなり違う気がしています。あくまで優先されているのは暫定最短距離の短さだからです。

Wikipediaには「最良優先探索（Best-First Search）」なる言葉が載っていて、こちらであれば完璧に当てはまります。偶然にもどちらも略語はBFSになってしまいますね。

もちろん多くの文脈では幅優先探索をBFSと略しても誤解はないと思います（私も使います）が、このように最短路問題における特殊化・一般化について述べる際には指しているものが曖昧になりやすいので、意識して区別するようにしています。