わかりやすく グラフ データ構造 とは

関係を点と線で入れる

ここまでは、値を列や表、ツリーに入れる方法を見てきました。でも、データによっては、値の一つひとつよりも値どうしの関係のほうが大事なことがあります。だれとだれが友だちか、どの駅とどの駅がつながっているか、といったことです。
こういうときは、一列に並べるのは不自然です。そこで、人を点に、友だちどうしを線にして描きます。点はノード、線はエッジとも呼び、点と線だけで関係がそのまま入ります。

二人を順に押して、線でつないでみましょう。点は人、線は友だち関係です。

点をつなぐと、関係が目に見えるようになりました。だれとだれがつながっているかは、線を見ればすぐにわかります。表に一行ずつ書くより、ずっと絵のように伝わります。
点は対象、線は関係。この二つで入れたデータをグラフと呼びます。友だちのようにおたがいに向き合う関係は向きのない線で、だれかがだれかをフォローするような片方向の関係は矢印の線で描きます。では、この線をたどると何がわかるのでしょうか。

線をたどって友だちの友だちへ

一人から始めてみましょう。その点につながった線をたどると、その人の友だちが出てきます。そこで止まらずに、友だちの点につながった線をまたたどると、友だちの友だちが出てきます。
こうして一歩ずつ遠くへ行けば、知り合いの知り合いにまで届きます。SNSが「知り合いかも」と友だちをすすめてくるのも、このやり方です。

一人を押すと友だちが、もう一度押すと友だちの友だちが、順に明るくなります。

一回押すと友だちが、もう一回押すと友だちの友だちが明るくなりました。始めた人からどれだけ離れているかは、線を何回たどったかで決まります。
線を一回たどれば友だち、二回たどれば友だちの友だちです。表だったら、これを知るために何度も見直していたでしょう。線をたどれば、こんなにかんたんです。

隣をたどって群れを見て回る

一つの点に線でじかにつながった点を、その点の隣といいます。一つの点から隣へ、またその隣の隣へと、線をたどって広がっていってみましょう。
そのうち、もう行くところがなくなります。そこまでにたどり着いた点が、おたがいにつながった一つの群れです。線でつながっていない点は、その群れには入りません。近い隣から一層ずつ広げていくこの方法を、幅優先探索といいます。

明るくなった群れの端にある隣を押して、一歩ずつ広げてみましょう。つながった点だけが明るくなります。

隣をたどって広がると、つながった点が次々に明るくなりました。線が届くところは、すべて見て回れました。反対に、離れた点はどこまで行っても明るくなりませんでした。
線でつながっているかどうかが、群れを分けるのです。隣をたどることは、グラフでは線を見るだけなのでかんたんです。では、同じことを表でしたらどうなるでしょうか。

表でするか、グラフでするか

友だち関係を表に書いたとしましょう。友だちの友だちを探すには、まず表で自分の友だちを探して書き出し、その友だち一人ひとりについて、また表を見直さなければなりません。一段先へ進むたびに、表をもう一度見ていくわけです。
グラフなら、点から線をたどり、その点からまた線をたどれば終わりです。関係がかなめのときは、グラフのほうがずっと便利です。

同じ「友だちの友だち」という問いを、表とグラフで解いてみましょう。押す回数が何回かかるかを比べます。

表では、同じ答えを探すのに押す回数がずっと多くかかりました。調べることをくり返さなければならなかったからです。グラフは、線を二回たどれば終わりました。
もちろん、表が悪いわけではありません。一行ずつ記録して集めるには、表が向いています。ただ、関係をたどる仕事なら、点と線で入れたグラフのほうがずっと自然で速いのです。地図アプリが道を探すときも、駅や道を点と線にして、線ごとに距離を書いたグラフを使っています。

まとめ

一言でまとめるとこうです。対象を点に、関係を線にして入れたものがグラフです。一つの点から線をたどると隣が出てきて、隣をまたたどると友だちの友だちが出てきます。
線をたどって広がれば、つながった群れが見えます。関係がかなめの仕事では、表を何度も見直す代わりに、線をたどるだけですみます。点=対象、線=関係、そして隣をたどること、これがグラフです。

要点を順に押して振り返りましょう。（点 = 対象、線 = 関係 → 友だちの友だち → 隣をたどる → 関係にはグラフ）

これで、関係を点と線で入れて、線をたどって巡る方法がわかりました。表では扱いにくかった友だちの友だちも、グラフなら線二本で届きました。データをどんな形に置くかによって、同じ仕事がやさしくもむずかしくもなるのです。
ところで、データベースに何かを尋ねるには、決まった言葉で尋ねなければなりません。次のレッスンでは、データベースに質問するための言葉、SQLを学びます。