何か優先探索
ここまではグラフに対する局所的な操作のみを考えてきましたが、ここからはグラフ全体に関する操作や性質を考えます。グラフ全体に関係する最も基礎的な性質は到達可能性 (reachablity) です。到達可能性問題では、グラフ \(G\) と頂点 \(s\) が与えられたときにどの頂点が \(s\) から到達可能か、つまり \(s\) からの路が存在する頂点はどれかを考えます。まずは無向グラフを考え、有向グラフは節の終わりで軽く触れることにします。無向グラフでは、\(s\) から到達可能な頂点は \(s\) の成分に含まれる頂点に等しくなります。
再帰的に考えることに慣れている私たちのような人にとって、到達可能性問題に対する最も自然なアルゴリズムは次に示す深さ優先探索 (depth-first serach, DFS) です。このアルゴリズムは再帰的にも手続き的にも書くことができ、どちらの方法を使ってもアルゴリズムは全く同じです。唯一の違いは、再帰的でないバージョンでは "再帰" スタックを実際に見ることができる点です。
procedure \(\texttt{RecursiveDFS}\)(\(v\))
if \(v\) に印が付いていない then
\(v\) に印を付ける
for \(vw\) の形をした辺 do
\(\texttt{RecursiveDFS}\)(\(w\))
procedure \(\texttt{IterativeDFS}\)(\(s\))
\(\texttt{Push}\)(\(s\))
while スタックが空でない do
\(v \leftarrow\)\(\texttt{Pop}\)()
if \(v\) に印が付いていない then
\(v\)に印を付ける
for \(vw\) の形をした辺 do
\(\texttt{Push}\)(\(w\))
深さ優先探索は、私が何か優先探索 (whatever-first search) と呼ぶ一般的なグラフ走査アルゴリズムのクラスに属する (おそらくは一番有名な) アルゴリズムです。何か優先探索という一般的なグラフ走査アルゴリズムでは、候補となる辺を「袋 (bag)」と私が呼ぶデータ構造に保存します。この「袋」が持つべき機能は一度入れたものを後で取り出す機能だけです。スタックは袋の具体的な例ですが、もちろん、袋となれるのはスタックだけではありません。
一般的な何か優先探索アルゴリズムを次に示します:
procedure \(\texttt{WhateverFirstSearch}\)(\(s\))
袋に \(s\) を入れる
while 袋が空でない do
袋から頂点を取り出して \(v\) とする
if \(v\) に印が付いていない then
\(v\) に印を付ける
for \(vw\) の形をした辺 do
\(w\) を袋に入れる
\(\textsc{WhateverFirstSearch}\) が \(s\) から到達可能な頂点全てに印をつけ、それ以外の頂点に印をつけないことをこれから示します。このアルゴリズムが \(G\) に含まれる全ての頂点に最大でも一回ずつ印をつけるのはすぐに分かります。一方で \(s\) から到達可能な全ての頂点に少なくとも一回印が付くことを示すには、アルゴリズムを次に示すように少し変更する必要があります。赤く示されたこの変更を行うと、最初に頂点 \(v\) を訪れたときに、\(v\) を袋に入れたときに処理していた頂点を思い出すことができます。以降この頂点を \(v\) の親 (parent) と呼びます。
procedure \(\texttt{WhateverFirstSearch}\)(\(s\))
袋に \(\color{red}{(\varnothing, s)}\) を入れる
while 袋が空でない do
袋から要素を取り出して \(\color{red}{(p, v)}\) とする \((\star)\)
if \(v\) に印が付いていない then
\(v\) に印を付ける \((\dagger)\)
\(\color{red}{\mathit{parent}(v) \leftarrow p}\)
for \(vw\) の形をした辺 do
\(\color{red}{(v, w)}\) を袋に入れる \((\star \star)\)
命題 5.1 \(\textsc{WhateverFirstSearch}\) は \(s\) から到達可能な全ての頂点に印をつけ、それ以外の頂点に印をつけない。そして、\(\mathit{parent}(v) \neq \varnothing\) である全ての \((v, \mathit{parent}(v))\) の組の集合は \(s\) を含む成分の全域木を定義する。
証明 \(s\) から到達可能な頂点 \(v\) 全てに印が付くことをまず示す。\(s\) から \(v\) への最短路の長さについての帰納法を用いる。まず、アルゴリズムは \(s\) に印をつける。\(v\) を \(s\) から到達可能な頂点とし、 \(s\) から \(v\) への最短路を \(s \rightarrow \cdots \) \(\rightarrow u \rightarrow v\) とする (\(v\) が \(s\) から到達可能なことから、この路は必ず存在する)。接頭部分 \(s \rightarrow \cdots \rightarrow u\) は \(s\) から \(v\) への最短路よりも短いから、帰納法の仮定よりアルゴリズムは \(u\) に印をつける。 \(u\) に印が付くとき、アルゴリズムはその後すぐに \((u, v)\) を袋に入れ、後で取り出される。\((u, v)\) を袋から取り出したとき、既に印が付いていない限り \(v\) には印が付けられる。よって示せた。
\(\mathit{parent}(v) = \varnothing\) を満たす組 \((v, \mathit{parent}(v))\) は \(G\) における辺である。印の付いた任意の頂点 \(v\) について、親をたどって行く路 \(v \rightarrow \mathit{parent}(v) \) \(\rightarrow \mathit{parent}(\mathit{parent}(v))\) \(\rightarrow \cdots\) がいつか \(s\) に戻ることをこれから示す。頂点に印がつけられた順番についての帰納法で示す。\(s\) が \(s\) から到達可能なのは自明だから、\(v\) を印の付いた \(s\) 以外の頂点とする。帰納法の仮定より \(\mathit{parent}(v) \rightarrow\) \(\mathit{parent}(\mathit{parent}(v)) \rightarrow \cdots\) は \(s\) に戻ってくる。この路に最初の部分に辺 \(v \rightarrow \mathit{parent}(v)\) を加えれば求めたい路が得られる。よって示せた。
このことから、\(s\) から到達可能な全ての頂点には印が付き、印の付いた頂点とその親を結ぶ辺を全て合わせると連結なグラフとなる。\(s\) 以外の印の付いた頂点はただ一つの親を持つので、このグラフの辺の数は頂点の数より \(1\) 小さい。すなわち、親をたどる辺が作るこのグラフは木である。 \(\Box\)
解析
この走査アルゴリズムの実行時間は "袋" のデータ構造に依存するので、袋に一つの要素を挿入する操作と袋から要素を取り出す操作の実行時間を \(T\) とします。\((\dagger)\) は印の付く頂点に対して一度ずつ実行されるので、最大でも \(V\) 回実行されます。また \(s\) の成分に含まれる辺 \(uv\) は (組 \((u,v)\) および \((v, u)\) として) 二度袋に入れられるので、\((\star \star)\) は最大でも \(2E\) 回実行されます。最後に、袋に入れた回数よりも多く袋から取り出すことはできないので、\((\star)\) は最大でも \(2E + 1\) 回実行されます。したがって、\(G\) が標準的な隣接リストで与えられるという仮定の下では、\(\textsc{WhateverFirstSearch}\) の実行時間は \(\pmb{O(V + ET)}\) です (もし隣接行列を使うなら実行時間は \(O(V^{2} + E T)\) です)。