モテるアルゴリズム講座　第1回グラフでモテたい

｜2010年03月05日（金）15:00｜amakata

天方です。

今日からモテるアルゴリズム講座を始めたいと思います。

それでは、第1回グラフでモテたいの講義を始めようと思います。
なんといってもアルゴリズムができるとかいうと、いろいろモテます。
この講座を通じて、皆さんもアルゴリズムをマスターしてモテてください。

本日は、モテるアルゴリズムを考える上で重要な
グラフのデータ構造について話をしたいと思います。

グラフというと、普通思い浮かべるのは棒グラフとか円グラフとかかもしれませんが、今回は違います。そんな反応をしていると婚期を逃します。

グラフというのは、点と枝かつながってできるものをグラフと言います。

グラフの例

グラフはいろいろな分野で使われていると思いますが、
あのGoogleも検索エンジンのページの順位付けのためにグラフの概念を利用していたいりします。

さて、グラフをコンピュータ上で扱おうとすると、そのデータ構造の持たせ方に悩みます。
グラフ用のライブラリを使えばそれほど大変でもないのですが、やはり自分で書いた方がモテます。

グラフをデータとして表現するにはいくつか方法があります。
では、上記の図で示したグラフをさまざまなデータ構造で表現してみようと思います。

まず、上の図の点と枝を数学的な表現を使って次のように表現することにします。

点の集合 $V=\{v_1,v_2,v_3,v_4,v_5,v_6\}$

枝の集合 $E=\{e_1,e_2,e_3,e_4,e_5,e_6,e_7,e_8,e_9,e_{10}\}$

その場合、点と枝の接続関係は次のようになります。

枝, 始点, 終点
$e_1,v_1,v_2\\e_2,v_2,v_4\\e_3,v_3,v_4\\e_4,v_4,v_5\\e_5,v_5,v_6\\e_6,v_6,v_1\\e_7,v_1,v_3\\e_8,v_5,v_2\\e_9,v_3,v_6\\e_{10},v_1,v_1$

ちなみに、向きがある枝でできたグラフを有向グラフと呼びます。
向きがない枝でできたグラフを無向グラフと呼びます。

こういったグラフを表現するデータ構造としては、枝の始点と終点の番号の組を持たせることでグラフを表現する方法があります。

それではこのグラフのデータ構造をRubyをつかって表現してみましょう。

例えば、上記の視点と終点をRubyの配列で表現すると下記のようになります。

start_vertex = [1,2,3,4,5,6,1,5,3,1]
end_vertex = [2,4,4,5,6,1,3,2,6,1]

これは、さきほど示した数学的な表現だと下記のような表現になります。
$start\_vertex=[v_1,v_2,v_3,v_4,v_5,v_6,v_1,v_5,v_3,v_1]\\end\_vertex=[v_2,v_4,v_4,v_5,v_6,v_1,v_3,v_2,v_6,v_1]$ … ①

配列の添え字が、枝の添え字 – 1になります。

頂点間に枝があるかどうかを調べるには
頂点数をnとすると $O(n)$ の計算量(時間的)がかかります。
また、計算量(空間的)は枝数を $m$ とすると $2m$ です。

そこで、各頂点毎に、出入りする枝を持つという手があります。

たとえば、下記の様な図のように一つの頂点に出入りする枝に注目します。

頂点v1に入る枝と出る枝の例

これはRubyで表現すると下記のようになります。

start_edge = [[1, 7, 10], [2], [3, 9], [4], [5, 8], [6]]
end_edge = [[6, 10], [1, 8], [7], [2, 3], [4], [5, 9]]

数学的な表現では下記のようになります。
$start\_edge=[[e_1,e_7,e_{10}],[e_2],[e_3,e_9],[e_4],[e_5,e_8],[e_6]]\\end\_edge=[[e_6,e_{10}],[e_1,e_8],[e_7],[e_2,e_3],[e_4],[e_5,e_9]]$ … ②

これで、頂点と枝の両方から検索ができるデータ構造ができました。ここモテます。
でも、もうすこしハイクラスのモテを期待したい場合は、クラスを利用したほうがいいと思います。

さて、配列でグラフを表現できるとからモテモテだと思っていい気になってはいけません。
やはりグラフを表現する場合にもTPOがあります。
例えば、他のラフの表現方法としては、接続行列を使う方法もあります。

接続行列 $M=\left\( \begin{array}{ccc} 1 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0\ -1 & 1 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0\ 0 & 0 & 1 & 0 & 0 & 0 & -1 & 0 & 1 & 0\ 0 & -1 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\ 0 & 0 & 0 & -1 & 1 & 0 & 0 & 1 & 0 & 0\ 0 & 0 & 0 & 0 &-1 & 1 & 0 & 0 & -1 & 0\ \end{array} \right)$ … ③

縦の座標が頂点の添え字、横の座標が枝の添え字に対応し、
要素が1であれば、その頂点を始点、要素が-1であれば、その頂点を終点とすることを表現しています。
この場合、計算量(空間的)は $nm$ です。頂点間に枝があるかを調べる計算量(時間的)は $O(m)$ です。
ちなみに、接続行列だと、自己ループしている枝を表すことができません。
そういえば、さきほどの配列を用いた、枝の始点と終点の番号の組のデータ構造だと、枝がない頂点を表現できません。
そこらへんについて、「ちょっときみ、そのデータ構造だと、自己ループが表現できないので、今回の案件には使わない方がいいと思うよ」と
それとなく耳打ちできるとそれとなくモテます。

他に隣接行列で表現する方法もあります。

隣接行列 $A=\left\( \begin{array}{ccc} 1 & 1 & 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 & 0 & 1 \ 0 & 0 & 0 & 0 & 1 & 0 \ 0 & 1 & 0 & 0 & 0 & 1 \ 1 & 0 & 0 & 0 & 0 & 0 \ \end{array} \right)$ … ④

これは、縦の座標を始点の頂点の添え字に対応させ、横の座標を終点の頂点の添え字に対応させて表現したもので、1なら接続している、0なら接続していないという表現です。この場合、計算量(空間的)は $n^2$ です。頂点間に枝があるかを調べる計算量(時間的)は $O(1)$ です。
みなさん、もうお気づきとは思いますが、隣接行列では、同じ始点、終点をもつ複数の枝を表すことができなくなります。

さて、４種類ほど表現方法を扱いましたが、それぞれの表現では、表現できるパターンの制約や、グラフを参照、更新する場合の計算量（時間的、空間的）などが違います。
シチュエーションや、相手の好みによって、表現方法を変えるとモテまくります。

みなさんもグラフでモテてみませんか？

この記事に関するお問い合わせはこちら

Webシステム開発の株式会社フラッツ

モテるアルゴリズム講座　第1回グラフでモテたい｜Webシステム開発の株式会社フラッツ

FLATzブログ