解説 7月5日B

今回の学習項目です。


グラフの探索

グラフの探索とは、グラフGと頂点v0が与えられたときに、グラフGのすべての頂点のリストを求めることです。 ここでグラフGは、隣接頂点関数Tによって表現されます。 つまり、T(v0)によってv0に隣接する頂点すべてがわかります。さらにこれらの頂点に対して隣接頂点関数Tの値を求めることにより、より広い範囲の頂点が求まります。これを次々に行うことにより、グラフGのすべての頂点が求まる(ただし、v0から枝をたどっていける頂点に限る)、という考えです。

これをアルゴリズムとして書いたものが以下です:

アルゴリズム GRAPH-SEARCH
入力: グラフGを表す隣接頂点関数T、初期頂点v0
出力: Gのすべての頂点のリスト(配列)
手続き:
    1. 頂点をいれるための入れ物A,Bを用意する。それらを空にする。
   (言い換えれば、空の入れ物A,Bを用意する)
    2. v0をAとBに入れる
    3. Aから一つの頂点を取出す。それを変数vの値とし、以下を行う:
        T(v)に属す頂点でBに入っていないものがあれば、それをすべてAとBに入れる
    4. Aが空ならBを出力して終了。さもなければステップ3へ。
ここで「入れ物」と書いてあるが、どのようなものが「入れ物」として使えるか、 また「入れ物」の種類によってグラフ探索の振る舞いや結果にどのような違いが出てくるか、を学ぶのが今回の主題である。

実は「入れ物」として使えるデータ構造は今までにたくさん学んできた。 例えば、配列、リスト、ハッシュ、ヒープ、キュー、スタックが「入れ物」として使える。 これらの違いは、例えばハッシュの場合、その入れ物に何が入っているか(探索)を効率よく答えることができるとか、キューとスタックに見られるように、その「入れ物」から要素を取り出す順番に特徴があるということにある。

課題1-1

本講義では、上記のアルゴリズムの入れ物Bとして、今まで学んだデータ構造のなかでハッシュを使うことを考えている。 どのような理由からハッシュを選んだのだろうか、考えられる理由を述べよ。

課題1-2

本講義では、上記のアルゴリズムの入れ物Aとして、キューとスタックの2種類を使うことを考えている。 このアルゴリズムにおいて、キューとスタックそれぞれを使った場合、アルゴリズムの振る舞い(結果として入れ物Bに入っている頂点の順番)にはどのような違いがあるだろうか、考えて答えよ。

グラフの探索の実装

前項で学んだアルゴリズムをRubyのプログラムとして実装しよう。

まず考えなければならないのは、グラフの表現である。木と同様に頂点クラスを作り、 それぞれの頂点に「隣接頂点」を付随させるというのが一つの方法として考えられる。 もうひとつの方法としては、頂点をラベルを表す文字列とし、「隣接頂点関数」をハッシュを用いて表現する、という方法がある。ここでは後者の方法を採用することとする。 次はそのコードである。ここで、グラフとして教科書図6.1のグラフを対象としている: (注: 大文字から始まる名前(例えばAdjacentNodes)は「変数」ではなく「定数」を表す---一度値をセットしたら変更できないものです)

 # 対象とするグラフ
 # V = {v1, v2, v3, v4}                              は ["v1","v2","v3","v4"] として表現
 # E = {{v1,v2}, {v2,v3}, {v1, v3}, {v3,v4}}
 #
 AdjacentNodes = {"v1" => ["v2", "v3"], "v2" => ["v1","v3"], "v3" => ["v1","v2","v4"], "v4" => ["v3"]}

課題2-1

ハッシュ AdjacentNodes のキーすべてからなる配列を返すコードをかけ。 またこれはこのグラフの何を表しているか、答えよ。
(ヒント: ハッシュについては6月7日Aの内容を思い出してみよう)

課題2-2

変数 retrieved (「探索済み」という意味) をハッシュとする。 グラフ探索によって取り出された頂点(ラベル)をvとして、以下の問に答えよ:

課題2-3

教科書図6.8(p.69)のグラフを表すRubyのコードをかけ。 ただし、ここで議論したように、ハッシュを用いて隣接頂点関数を表す方法を持ちいよ。

[グラフの表現:ハッシュを用いた隣接頂点関数による方法]
先にあげたコードを例に説明します。
 # 対象とするグラフ
 # V = {v1, v2, v3, v4}                              は ["v1","v2","v3","v4"] として表現
 # E = {{v1,v2}, {v2,v3}, {v1, v3}, {v3,v4}}
 #
 AdjacentNodes = {"v1" => ["v2", "v3"], "v2" => ["v1","v3"], "v3" => ["v1","v2","v4"], "v4" => ["v3"]}
AdjacentNodes は隣接頂点関数として働きます。これは、グラフにおいて、 どの頂点がどの頂点とつながっているかを表しています。例えば AdjacentNodes("v1")は値として["v2", "v3"]を返します。 これは頂点v1v2v3につながっていることを 表します。また、AdjacentNodes("v2")は値として["v1", "v3"]を返します。 これは頂点v2v1v3につながっていることを表しています。 このように、どの頂点がどの頂点とつながっているかを表した隣接頂点関数によって グラフが再現できる、言い換えれば、AdjacentNodesのようなハッシュによって グラフを表している、ということです。

課題2-4

課題2-3で表現したグラフを対象とし、「入れ物」Aとしてキューを用いて、 グラフ探索アルゴリズムをRubyのプログラムとして実現し、その結果を示せ。 ただし、複数の頂点を入れる場合は、番号の若い方を先にいれるものとする。

[キューの扱い]
キューを作るには6月14日Aの講義で作成したQueueクラスを使います。 新しくキュー(のインスタンス)を作るには、例えば、 a = Queue.new(100)とします。ここで100とは、このキュー(a)で記憶できるデータの最大個数を100としたことを表します。
また、このキュー(a)に v の値を入れるには、 a.enqueue(v) とします。ここでキュー(a)に入れる場合には、一個一個いれる しかできないことに注意してください。
さらに、このキュー(a)から取り出して、取り出したものを変数xの値にするには、 x=a.dequeue()とします。

課題2-5

課題2-3で表現したグラフを対象とし、「入れ物」Aとしてスタックを用いて、 グラフ探索アルゴリズムをRubyのプログラムとして実現し、その結果を示せ。 ただし、複数の頂点を入れる場合は、番号の若い方を先にいれるものとする。
また、この結果と課題2-4の結果と比較せよ。

[スタックの扱い]
スタックを作るには6月21日Aの講義で 作成したStackクラスを使います。 新しくスタック(のインスタンス)を作るには、例えば、 a = Stack.new()とします。そして、このスタック(a)に v の値を入れるには、 a.push(v) とします。ここでスタック(a)に入れる場合には、一個一個いれる しかできないことに注意してください。
さらに、このスタック(a)から取り出して、取り出したものを変数xの値にするには、 x=a.popup()とします。


「アルゴリズムとデータ構造」のホームに戻る