情報科学と人工知能のノート

初等的な知識から最新論文の解説まで色々集めていきます.備忘録兼用.

深さ優先探索

深さ優先探索はグラフを探索するためのアルゴリズムです*1.注意書きの通り、細かいことを言うと面倒なのですが、以下ではグラフ上の二頂点間の連結性を判定するアルゴリズムだと思って説明を進めましょう.

定義

  • 入力:グラフ G=(V,E)、始点 s \in V、終点 t \in V
  • 出力:st が連結なら 1、そうでなければ 0.

直観的な説明

与えられたグラフが迷路だと思って、それをごくごく人間的に解くやり方が正に深さ優先探索です.すなわち、

  1. 始点からどんどん進んでいく.
  2. 分かれ道に行き当たったら、どれか一つ選んでどんどん進む.
  3. 行き止まりにたどり着いたら、分かれ道まで戻り、別の道を進む.
  4. 終点にたどり着くまで 2 と 3 を繰り返す.

という感じです.始点と終点および分かれ道がグラフの頂点、それらを結ぶ道(一方通行でも良い)がグラフの辺です.ただし、分岐は入れ子になっている場合が多いため、どの分岐をどっちに進んだのかを逐一覚えておかなければいけません.例えば、

  1. 始点から進んでいったら3つに分かれた分かれ道にたどり着く.この分岐を分岐Aと名付け、3つの道をそれぞれA1、A2、A3と名付ける.
  2. 道A1を進んでいったら2つに分かれた分かれ道にたどり着く.この分岐を分岐Bと名付け、2つの道をそれぞれB1、B2と名付ける.
  3. 道B1を進んでいったら行き止まりにたどり着く.分岐Bに戻る.
  4. 道B2を進んでいったら行き止まりにたどり着く.分岐Bに戻る.
  5. 分岐Bの2つの道はどちらも行き止まりだったので分岐Aに戻る.
  6. 道A2を進む.
  7. ……

という感じです.また、同じ道を何度も辿らないように一度来たところには印をつけておくことも必要です.

擬似コード

以上をまとめると、アルゴリズムは以下のようになります.

C[v] \leftarrow 0, \forall v \in V;
S \leftarrow \{ s \}; // S はスタック
C[s] \leftarrow 1;
{\rm while} \  S \neq \emptyset
  v \leftarrow \ S の一番上の要素; // ポップはしない(取り出さない)
  {\rm if} \  \exists u \in V \  {\rm s.t.} \  (v, u) \in E \  {\rm and} \  C[u] = 0
    Su をプッシュ(一番上に要素を載せる);
    C[u] \leftarrow 1;
  {\rm else}
    S をポップ(一番上の要素を取り除く);
{\rm return C[t];

ただし、時間計算量を分かりやすく求めるためには、人間で考えると少し可笑しいのですが下のように書いた方がよいと思います.

C[v] \leftarrow 0, \forall v \in V;
S \leftarrow \{ s \}; // S はスタック
C[s] \leftarrow 1;
{\rm while} \  S \neq \emptyset
  v \leftarrow \ S をポップ;
  {\rm for} \  u \in V \  {\rm s.t.} \  (v, u) \in E
    {\rm if} \  C[u] = 0
      Su をプッシュ;
      C[u] \leftarrow 1;
{\rm return C[t];

計算量

下の擬似コードで考えましょう.n = |V|m = |E| とおきます.

時間計算量から求めます.
まず、C の値が 0 の頂点しかスタックに積まれないこと、そしてスタックへのプッシュと C の値変更が必ず対になっていることから、ある頂点がスタックに積まれるのは高々一回です.積まれるのが高々一回なので、取り出されるのも高々一回です.while 文はスタックが空でないときにのみ回り、一回回るごとに必ず一つの要素が取り出されるため、まとめると while 文は高々 n 回しか回らないことになります.また、頂点同士の接続関係が隣接リストで与えられているものとすると、while 文の内側の for 文はアルゴリズム全体で高々 O(m) 回しか回りません(有向グラフのとき m、無向グラフのとき 2m).なぜならば、スタックから v_1 \in V が取り出されたとき v_1 と接続されている頂点の個数だけ回り、v_2 \in V が取り出されたとき v_2 と接続されている頂点の個数だけ回り、…というのを全部足すと O(m) になるからです.まとめると、上記の擬似コードの合計ステップ数は O(n + m) になります. n \leq m なのは当たり前だと思って O(m) と書く場合もあります.

定数個の作業変数を除くと、上記の擬似コードでは CS の分のメモリが必要となります.C は明らかに O(n) ワード必要で、上記の通り while 文が最大で n 回回ることから最悪時の S のサイズも O(n) ワードです.まとめると結局全体でも O(n) ワードのメモリが必要となります.

一つ目の擬似コードでは、if 文の条件を満たす頂点を求めるために時間計算量が一見 O(n + m) に収まらないように見えますが、もう一つデータ構造を追加して、各頂点についてその隣接リストをどこまで参照したかを覚えておくと、やはり時間計算量 O(n + m)、空間計算量 O(n) で動かすことができます.
更に、一つ目の擬似コードのアルゴリズムを少し変形すると、グラフの最大分枝度(branching factor:outdegree(出次数)と一緒)b、始点から作ることのできるパスの最大長さを l とおいたときに、時間計算量 O(b^l)、空間計算量 O(l) のアルゴリズムを作ることができます.b^l は大抵 n よりも大きいですし(場合によっては指数的に大きい)、l もどうせ最悪で n なのですが、特定のグラフ(木が代表的な例)ではそこそこの時間で動く非常にメモリ効率の良いアルゴリズムとなります.ちなみに、二つ目の擬似コードを同じように変形すると、空間計算量は O(bl) になります.

*1:細かいことをいうと、厳密には深さ優先探索は「アルゴリズム」ではないと思います.アルゴリズムとは、問題、すなわち特定の入力と出力の組、に対して入力から出力を求めるための(実装上の微妙な差異はさておき)一つばっちり定まった解法のことです.一方、世の中の人々は、二頂点間の連結性判定や強連結成分の抽出とかグラフ上の頂点の順序付けとか経路探索や、微妙に違う問題(全然違うわけではない)を解くそれぞれのアルゴリズムを、単に同名なだけでなく全て同じものだという意識を持って、一緒くたに深さ優先探索アルゴリズムと呼んでいるのです.何故それらのアルゴリズムがまとめて深さ優先探索と呼ばれるかというと、それらがグラフを帰りがけ順(post order)で探索するからです.「深さ優先探索」という言葉に出会ったら、それは単に帰りがけ順の言い換えなんだと思っておけば間違いないです.このように複数のアルゴリズムをまとめて一つの名前で呼んでいるケースは幅優先探索など他にもいくつかありますが、今後ブログ内では一般的な流儀に従ってそれらを単にアルゴリズムと呼びます.