グラフデータの基本的アルゴリズム(DFS、BFS、ニ部グラフ判定、最短路問題、最小全域木)

サマリー

「問題解決のアルゴリズム活用とコーディングのテクニックを鍛える」より。グラフデータの基本的アルゴリズム(DFS、BFS、ニ部グラフ判定、最短路問題、最小全域木)について述べる。

深さ優先探索

まず深さ優先探索(DFS:Depth-First Search)について。DFSとは、探索の手法の一つとなる。ある状態からはじめ、遷移できなくなるまで状態を進めていき、遷移できなくなったら一つ前の状態に戻ると言うことを繰り返して解を見つける。例えば数独なら、適当なマスの値を決めて、また他のマスの値を決めて、と進めていき、解に到達できなければ直前の一手をやめて、また適当なマスの値を決めていくというふうになる。深さ優先探索は、その性質上再起関数で容易に解けることが多い。

ここで再帰関数は、関数の中で同じ関数を呼び出すことをいう。たとえば、階乗を計算する関数int fact(int n)を作りたいとしたとき、n!=nx(n-1)なので以下のように書くことができる。

int fact(int n) {
  if (n == 0) return 1;
  return n * fact(n-1);
}

再帰関数を書くときには、必ず関数が停止するように作る必要がある。先ほどの例では、n=0のときはfactを再起呼び出しするのではなく直接1を返している。この条件がないと無限に関数を呼び出してしまいプログラムが暴走する。

深さ優先探索は、一番初めの状態から遷移を組み替えすことでたどり着ける全ての状態を生成する。従って、すべての状態に対して操作を施したり、全状態を列挙することができる。

深さ優先探索では基本的にスタック(Stack)を使うこととなる。スタックは、pushとpopという2つの操作ができるデータ構造でpushはスタックの一番上にデータを積む操作、popは逆にスタックの一番上からデータを取り出す操作となる。つまり最後に入れた要素を最初に取り出すのでLIFO(Last in First Out)と呼ばれる。

スタックは配列やリストを使って容易に作ることができるが、一般的なプログラミング言語では標準で用意されておりそれらを使えば良い。また、関数の呼び出しは通常スタックで実現されているため、前述の再帰関数は、再帰呼び出しの代わりにスタックを用いて書き直すこともできる。

幅優先探索

次に、幅優先探索(BFS:Breath-Fisrt Search)について述べる。BFSも基本的な探索の手法の一つとなり、深さ優先探索と同じく、ある状態からはじめて辿り着けるすべての状態を探索する。

深さ優先探索と異なる点は探索する順番で、幅優先探索では、はじめの状態に近いほうから探索する点にある。つまり。初めの状態→最短1回の遷移で辿り着ける全ての状態→最短2回の遷移で辿り着ける全ての状態→•••という順に探索していく。幅優先探索では同じ状態は一度しか通らないので、計算量はO(状態数x遷移の仕方)程度となる。

深さ優先探索でスタックが用いられていたのに対して、幅優先探索ではキューが用いられる。最初に、初期状態をキューに入れ、その後キューから状態を取り出し、そこから遷移できるすべての訪れたことのない状態キューに入れる、という操作をキューがからになるか、回が見つかるまで繰り返す。キューの様子をみて見てみると、初期状態に近い順に出てきていることがわかる。

ここでキュー(Queue)はスタックと同じように、pushとpopという2つの操作ができるデータ構造となる。スタックと違うのはpopが一番上から取り出すのではなく、一番下から取り出すということになる。つまり、最初にいれた要素が最初に出てくる。これをFIFO(First in First Out)と呼ぶ。

幅優先探索では初期状態から近い順に探索をするので、簡単に最短経路や最短手数などを求めることができる。状態がシンプルで例えば現在位置の座標だけの場合、pairを作ったりinit型にエンコードしたりして状態を表現することができる。状態がもっも複雑な場合は、クラスなどを作って状態を表現することも必要となる。遷移の仕方も平面的な移動では4方向だが、問題によって次元を考える必要がある。

幅優先探索では、すでに訪れたかを表すグラフだけを管理しておけば、試銭近い方から探索する。最短距離を求める問題の場合は最短距離を保存した配列を定義し、たとえばその配列を十分大きな定数INFで初期化しておくことで、まだ辿り着いていないところがINFとなり、フラグの役割も同時に果たすことができる。

ゴールに達した時点で探索は打ち切られるが、打ち切らないでキューがからになるまで続けると、各地点までの最短距離を計算することができる。また、最後まで探索して最短距離配列がINFになっている場合は、スタート地点から到達不能であることを意味するものとなる。

幅優先探索も、深さ優先探索と同じく辿り着けるすべての状態を生成する。従って、すべての状態に対して処理をしたい場合などにも幅優先探索を使う人ができる。しかし、再帰関数だと短くかけたり、状態を保存するのが簡単なので、深さ優先探索で描かれることが多い。一方、最短路を求めたい場合は、DFSでは同じ状態を何度も通ることとなるため、BFSを用いる。

以下にそれらを用いた基本的な木構造データのアルゴリズムについて述べる。

二部グラフ判定

まず「ニ部グラフ判定」について。これは頂点nの無向グラフが与えられ、隣接している頂点同士が違う色になるように、頂点に色を塗っていき2色以内ですべての頂点を塗ることができるかどうかを判定する」

隣接している頂点同士が違う色になるように彩色する問題を、グラフの彩色問題という。グラフを採食するのに必要な最小の色数をグラフ彩色数と言う。彩色数が2であるグラフをニ部グラフという。ニ部グラフは関係性データの学習をする際にベースとなる重要なグラフ構造となる。

2色で塗る場合、一つの頂点の色を決めれば隣接する頂点の色も一位的に決まる。従って適当な頂点からはじめて隣接する頂点の色を順次決めていけば、2色で濡れるかどうかが判定できる。これは深さ優先探索をもちいることで簡単に書くことができる。

もし。グラフが連結なら1回のDFSですべての頂点をみることができる。連結かどうかの判定や、木かどうかの判定などもDFSを少し拡張することで書くことができる。DFSを利用してトポロジカル順序を求めることもできる。

最短経路問題

次に最短路問題について述べる。最短路問題はグラフの最も基本的な問題となる。最短路とは2頂点が与えられたときに、その頂点を始点・終点とするようなパスのうちで、通る辺のコストを最小にするもののことをいう。コストを距離として、最短距離を考えるとわかりやすい。

ベルマンフォード法

まずベルマンフォード(Bellman-Ford)法について。始点を固定したときに、他のすべての頂点との間の最短距離を求める問題を単一始点最短距離問題と呼ぶ。さらに、終点を固定したものを祖父頂点対最短路問題と呼ぶが、同じ計算量で単一始点最短路問題が解けるので、単一始点最短露問題で解かれる。

始点sから頂点iへの最短距離をd[i]とする。すると、以下のような等式が成り立つ。

\[d[i]=min\{d[j]+(jからiへの辺のコスト)|e=(i,j)\in E\}\]

もし、グラフがDAGであれば、頂点を順序づけることができるので、この漸化式を用いてdを計算することができる。しかし、グラフに閉路が含まれている場合は順に計算していくことができない。その場合でもし仮の最短距離をd[i]とし、初期値d[s]=0、d[i]=INF(十分大きな定数)として、この式を繰り返し適用してdを更新していくことでdを計算することができる。閉路がなければこの更新はいつか停止し、その時のdは最短距離となる。

//頂点fromから頂点toへのコストcostの辺
struct edge { int from, to, cost;};

edge es{max_E];  //辺

int d[MAX_V];   //最短距離
int V, E;       //Vは頂点数、Eは辺数

// s番目の頂点から各頂点への最短距離を求める
void shortest_path(int s) {
  for (int i = 0; i < V; i++) d[i] = INF;
  d[s] = 0;
  while (true) {
     bool update = false;
     for (int i = 0; i < E; i++) {
        edge e = es[i];
        if (d[e.from] !=INF && d[e.to] > d[e.from] +e.cost) {
          d[e.to] = d[e.from] + e.cost;
          ipdate = true;
        }
      }
      if (!opdate) break;
    }
 }

このアルゴリズムを、ベルマンフォード(Bellman-Ford)法と呼ぶ。グラフにsから到達可能な負のコストの閉路がなければ最短路は同じ頂点を通らないので、たかだか|V|-1回しか実行されない。またこのアルゴリズムでは、すべてのiについて、d[i]=0と初期化すれば、すべてのふカイロの検出にも使える。

ダイクストラ法

次にダイクストラ法について述べる。負の辺がない場合で、ベルマンフォード法でd[i]が最短距離でない場合、d[j]=d[i]+(iからjの辺のコスト)と更新できたとしても、d[j]は最終的な最短距離にはならない。また、d[i]が変化していない場合でも、頂点iから出ている辺を毎回見ており、無駄となる。そこで以下のように修正する。

1. 最短距離が確定した頂点と隣接している頂点を更新する。
2. 1て使った「最短距離が確定した頂点」はもう使わない。

1と2のうち、最短距離が確定した頂点をどのように見つけるかが問題となる。初期状態では始点のみ最短距離が確定している。まだつか分けていない頂点のうち、距離d[i]が最小の頂点は最短距離が確定している。これは、負の辺がないのでd[i]のあとでより小さくなることがないめたとなる。このアルゴリズムをダイクストラ(Dikstra)法と呼ぶ。

int cost[MAX_V][MAX_V];  //cost[u][v]は辺e(u,v)のコスト(存在しない場合はINF)
int d[MAX_V];            //頂点sからの最短距離
bool used[MAX_V].        //すでに使われたフラグ
int V;

//始点aから拡張点への最短距離を求める
void dijkstra(int s) {
   fill(d, d + v, INF);
   fill(used, used + V, false);
   d[s] = 0;

   while(true) {
     int v = -1;
     //まだ使われていない頂点のうち距離が最小のものを探す
     for (int u = 0; u < V; u++) {
       if(!used[u] && (v == -1 || d[u] < d[v])) v = u;
     }
     if (v == -1) break;
     used[v] = ture;

    for (int u = 0; u < V; u++) {
      d[u] = min(d[u], d[v] +cost[v][u]);
    }
   }
 }

ワーシャル・フロイド法

最後にワーシャル・フロイド法について述べる。すべての2頂点間の最短路を求める問題を全点対最短路問題と呼ぶ。全点対最短路をDPで求める。頂点0〜kとi,jのみを使う場合の、iからjへの最短路をd[k+1][i][j]とする。k=-1のときはiとjのみを使うとして、d[0][i][j]=cost[i][j]とする。頂点0〜kのみを使う場合を頂点0〜k-1のみを使う場合に帰着させる。

頂点0〜kのみを使う時、iからjへの最短路は頂点kをちょうど一度通る場合と、全く通らない場合に分かれる。頂点kを通らない場合はd[k][i][j]=d[k-1][i][j]となる。頂点kを通る場合は、頂点iから頂点kへの最短路と頂点kから頂点jへの最短路に分解するので、d[k][i][j]=d[k-1][i][j]+d[k-1][k]i]となる。この2つを合わせると、d[k][i]j]=min(d[k-1][i][j],d[k-1][i]k]+d[k-1][k][i])となる。このDPは同じ配列を使いまわして、d[i][j]=min(d[i][j],d[i][k]+d[k][i])と更新していくことになる。

このアルゴリズムをワーシャル・フロイド(Warshall-Floyd)法と言い、O(|V|3)で全点対最短路を求めることができる。ワーシャル・フロイド法もベルマンフォード法と同様に負の辺があっても動作する。負の閉路があるかないかは、d[i][i]が負になる頂点iがあるかどうかで判別できる。

int d[MAX_V][MAX_V]; //d[u][v]は辺e=(u,v)のコスト(存在しない場合はINF、ただしd[i][i]=0とする)
int V; //頂点数

void warshall_floyd() {
  for (int k = 0; k < V; k++)
     for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++) d[i][j] = min[d[i][j], d[i][k] + d[k][j]);
}

非常に単純な3重ループで全点対最短路が求まる。実装が容易なため、計算量に余裕があれば、単一始点最短路問題の場合でもワーシャル・フロイド法を用いると良い

最小全域木アルゴリズム

次に最小全域木のアルゴリズムについて述べる。無向グラフが与えられたときに、その部分グラフで任意の2頂点を連結にするような木を全域木(spanning tree)と呼ぶ。辺にコストがある時ら、使われる辺のコストの和を最小にする全域木を最小全域木(MST;Minimum Spanning Tree)と呼ぶ。

例えば頂点を村、辺を建設予定の道路とするようなグラフを考えてみる。全域木は、すべての村を行き来できるように、ちょうど村の数-1本の道路を作ることに相当する。道路に建設費用がある場合、最小の建築費となるように全域木を作るのが最小全域木問題と考えられる。

最小全域木を求めるアルゴリズムとして、クラスカル(Kruskal)法とプリム(Prim)法と呼ばれるものが知られている。明らかに、全域木が存在することと連結であることとは同値なので、グラフは連結であると仮定する。

プリム法

まずプリム法による最小全域木問題について。プリム法はダイクストラ法と似ていて、ある頂点からはじめて少しずつ辺を追加していく方法となる。

まず、一つの頂点vのみからなる木Tを考える。ここから、貪欲的にTとその他の頂点を結ぶ最小コストの辺をTに付け加えることを繰り返して、全域木を構成していく。このようにして作られた全域木が最小全域木となることを証明する。

Vを頂点の集合とする。今X(⊂V)に対する全域木Tが求まっていて、Tを部分グラフとして含むような最小全域木が存在するとする。XとV\Xを結ぶ辺のうち、最小コストの辺を含むVの最小全域木で、かを部分グラフとするものが存在することを示す。最小コストの辺をeとし、v(∈X)となゅ∈V\X)を結んでいるとする。仮定からTを部分グラフとして含むようなVの最小全域木が存在する。eがこの最小全域木に含まれていれば何もいうことがないので、eは含まれていないとする。全域木は木なので、eを加えることで閉路ができる。

閉路に含まれる辺のうち、XとV\Xを結ぶ辺で、eとは異なる辺fが必ず存在する。eの散り方からfのコストはeのコスト以上になる。そこで全域木からfを取り除いてeを加えることにより新たな全域木が作れ、そのコストは元の全域木のコスト以下になる。よってeとTを含むようなVの最小全域木が存在することが言える。このことから、Tにeを付け加えても最初の仮定は満たされるので、次々辺をくわえていき、X=Vとなるまで続けることができる。Tを部分グラフとして含むようなVの最小全域木が存在するので、X=VならTはVの最小全域木になる。

int cost[MAX_V]{MAX_V}; //cost[u][v]は辺e=(u,v)のコスト(存在しない場合はINF)
int mincost[MAX_V];     //集合Xからの辺の最小コスト
bool used[MAX_V];       //頂点iがXに含まれているか
int V;                  //頂点数

int prim() {
  for (int i = 0; i < V; ++i) {
     mincost[i] = INF;
     used[i] = false;
  }

 mincost[0] = 0;
 int res = 0;

 while(true) {
   int v = -1;
   // Xに属さない頂点のうちXからの辺コストが最小になる頂点を探す
　　for (int u = 0; u < V; u++) {
      if (!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
   }
    
   if ( v == -1) break;
   used[v] = true;    //頂点vをXに追加
   res += mincost[v]; //辺のコストを加える

　　for (int u = 0; u < V; u++) {
     mincost[u] = mincost(mincost[u], cost[v][u]);
   }
  }
  return res;
}

クラスカル法

次にクラスカル法について述べる。クラスカル法は辺をコストの小さい順に見ていき、閉路(二重辺を含む)ができなければ追加すると言う手順をとる。

閉路ができるかどうかの判定は、頂点uと頂点vを結ぶ辺eを追加しようと考えているとすると、追加前にuとvが同じ連結成分に属していなければ、eを追加しても閉路はできない。逆にuとvが同じ連結成分に属していれば必ず閉路ができる。同じ連結成分かどうかはUnionFind木を使うことで効率的に判定できる。

struct edge{ int u, v, cost; };

bool comp(const edge& e1, const edge& e2) {
   return e1.cost < e2.cost;
}

edge es[MAX_E];
int V, E;     //頂点数と辺

int kryska() {
   sort(es, es + E, comp);  //egde.costが小さい順にソートする
　　init_union_find(V);      //Union-Findの初期化
　　init res = 0;
   for (int i = 0; i < E; i++) {
      edge e = es[i];
      if (!same(e.u, e.v)) {
         unite(e.u, e.v);
         res += e.cost;
      }
    }
    return res;
 }