アルゴリズムとデータ構造 2011年7月8日課題の復習 情報知能学科 白井英俊

グラフ探索の演習 図6.8(下図）に示すグラフに対するGraph-Searchの振る舞いをv6を始点として、(1)Aとしてキューを使った場合と、(2)スタックを使った場合のそれぞれに対して示せ。（複数の頂点をいれる場合は、番号の若い方を先にいれるものとする） v3 v0 v1 v2 v10 v11 v12 v5 v6 v4 v9 v8 v13 v7

グラフ探索（キューによるもの） Graph Search with QUEUE: v6 v5 v7 v4 v8 v12 v3 v9 v13 v2 v11 v10 v1 v0 v3 v0 v1 v2 v10 v11 v12 v5 v6 v4 v9 v8 v13 v7

グラフ探索（スタックによるもの） Graph Search with STACK: v6 v5 v7 v8 v9 v13 v3 v12 v2 v11 v1 v10 v0 v4 v3 v0 v1 v2 v10 v11 v12 v5 v6 v4 v9 v8 v13 v7

GRAPH-SEARCH (教科書、p.62) 入力： グラフGを表す隣接頂点関数Tと初期頂点v0 出力： Gのすべての頂点のリスト 手続き： 頂点を入れるための入れ物A,B（初期値は空） v0をAとBに入れる Aから一つの頂点vを取り出し「T(v)に属す頂点でBに入っていないものがあれば、AとBに入れる」 Aが空ならBを出力して終了。そうでなければ３へ。 ３の実現方法はいろいろ---p.62の方式を次に示す 5

(1)入れ物A, Bを用意する（続き) 配列、ハッシュ、キュー、スタックなどの「データ構造」は、newメソッドでインスタンスを作る 例 配列：　Array.new ハッシュ：　　Hash.new これらはRubyの組み込み （最初からある）のデータ構造 スタック： Stack.new キュー：　Queue.new 木： … これらはRubyの組み込みではない 別途Classの宣言が必要 しかし、newによってインスタンスを 作ることは同じ

キューとスタックの準備 キューのクラス queueX.rb スタックのクラス stackX.rb class Queue attr_accessor :head, :tail def enqueue(item) … end def dequeue … end def empty … end def find(item) … end end class Stack 　　　　　　　　　　 attr_accessor :data, :top def push(item) … end def popup … end def empty … end end

GRAPH-SEARCHプログラム(queue版) def graphSearchQ(v) # キューを用いたグラフ探索 check = Hash.new(false) # 頂点が記録済みかどうかのチェック用(B) agenda = Queue.new # 調査すべき頂点の記憶用(A) agenda.enqueue(v) # 始点vをAに入れる(enqueue) result = [v]　　　　　　　　　 # 始点vを訪問リストに入れる check[v] = true #始点vを記録済みとしてチェック while (! agenda.empty)　 　 　　　# 調査すべき頂点がある限り繰り返し v = agenda.dequeue # 次に調査すべき頂点(v)を取出す for w in v.adjacentNodes # vに隣接する頂点それぞれ(w)に対し if (! check[w]) # wが記録済みでなければ agenda.enqueue(w) # wを調査すべき頂点に登録(A) 　　　　　　　 check[w]=true # wを記録済みとして登録(B) result << w # wを訪問リストの末尾に入れる end # if end # for end # while return result # (すべての頂点を調査したので) 訪問リストを返す end # def 8

GRAPH-SEARCHプログラム(queue版) def graphSearchQ(v) # キューを用いたグラフ探索 check = Hash.new(false) # 頂点が記録済みかどうかのチェック用(B) agenda = Queue.new # 調査すべき頂点の記憶用(A) agenda.enqueue(v) # 始点vをAに入れる(enqueue) result = [v]　　　　　　　　　 # 始点vを訪問リストに入れる check[v] = true #始点vを記録済みとしてチェック while (! agenda.empty)　 　 　　　# 調査すべき頂点がある限り繰り返し v = agenda.dequeue # 次に調査すべき頂点(v)を取出す for w in v.adjacentNodes # vに隣接する頂点それぞれ(w)に対し if (! check[w]) # wが記録済みでなければ agenda.enqueue(w) # wを調査すべき頂点に登録(A) 　　　　　　　 check[w]=true # wを記録済みとして登録(B) result << w # wを訪問リストの末尾に入れる end # if end # for end # while return result # (すべての頂点を調査したので) 訪問リストを返す end # def 9

GRAPH-SEARCHプログラム(queue版) def graphSearchQ(v) # キューを用いたグラフ探索 check = Hash.new(false) # 頂点が記録済みかどうかのチェック用(B) agenda = Queue.new # 調査すべき頂点の記憶用(A) agenda.enqueue(v) # 始点vをAに入れる(enqueue) result = [v]　　　　　　　　　 # 始点vを訪問リストに入れる check[v] = true #始点vを記録済みとしてチェック while (! agenda.empty)　 　 　　　# 調査すべき頂点がある限り繰り返し v = agenda.dequeue # 次に調査すべき頂点(v)を取出す for w in v.adjacentNodes # vに隣接する頂点それぞれ(w)に対し if (! check[w]) # wが記録済みでなければ agenda.enqueue(w) # wを調査すべき頂点に登録(A) 　　　　　　　 check[w]=true # wを記録済みとして登録(B) result << w # wを訪問リストの末尾に入れる end # if end # for end # while return result # (すべての頂点を調査したので) 訪問リストを返す end # def 10

GRAPH-SEARCHプログラム(queue版) def graphSearchQ(v) # キューを用いたグラフ探索 check = Hash.new(false) # 頂点が記録済みかどうかのチェック用(B) agenda = Queue.new # 調査すべき頂点の記憶用(A) agenda.enqueue(v) # 始点vをAに入れる(enqueue) result = [v]　　　　　　　　　 # 始点vを訪問リストに入れる check[v] = true #始点vを記録済みとしてチェック while (! agenda.empty)　 　 　　　# 調査すべき頂点がある限り繰り返し v = agenda.dequeue # 次に調査すべき頂点(v)を取出す for w in v.adjacentNodes # vに隣接する頂点それぞれ(w)に対し if (! check[w]) # wが記録済みでなければ agenda.enqueue(w) # wを調査すべき頂点に登録(A) 　　　　　　　 check[w]=true # wを記録済みとして登録(B) result << w # wを訪問リストの末尾に入れる end # if end # for end # while return result # (すべての頂点を調査したので) 訪問リストを返す end # def 11

課題 queue版にならってstack版を作る（graphSearch.rbのgraphSearchS関数を完成させる） Stack.new 　　インスタンスを作る　Queue.new 　　データを追加（記憶）　enqueue 記憶したデータの取り出し　dequeue 空っぽかどうかの判定　empty Stack.new push popup empty

GRAPH-SEARCHプログラム(stack版) def graphSearchQ(v) # キューを用いたグラフ探索 check = Hash.new(false) # 頂点が記録済みかどうかのチェック用(B) agenda = Stack.new # 調査すべき頂点の記憶用(A) agenda.push(v) # 始点vをAに入れる(enqueue) result = [v]　　　　　　　　　 # 始点vを訪問リストに入れる check[v] = true #始点vを記録済みとしてチェック while (! agenda.empty)　 　 　　　# 調査すべき頂点がある限り繰り返し v = agenda.popup # 次に調査すべき頂点(v)を取出す for w in v.adjacentNodes # vに隣接する頂点それぞれ(w)に対し if (! check[w]) # wが記録済みでなければ agenda.push(w) # wを調査すべき頂点に登録(A) 　　　　　　　 check[w]=true # wを記録済みとして登録(B) result << w # wを訪問リストの末尾に入れる end # if end # for end # while return result # (すべての頂点を調査したので) 訪問リストを返す end # def 13