グラフと探索(Ruby)
- 作者: 川中真耶,杵渕朋彦,椎名俊輔
- 出版社/メーカー: アスキー・メディアワークス
- 発売日: 2012/05/30
- メディア: 大型本
- 購入: 5人 クリック: 34回
- この商品を含むブログ (6件) を見る
グラフと探索についてです。
まずグラフですが、本書での定義を書いておきます。
グラフ(Graph)G とは、頂点(Vertex)の集合 V と枝(Edge)の集合 E のペア(V, E) のことをいう。枝 e は始点 u と終点 v をもつペア e = (u, v) として表す。枝に向きがあるのを「有向グラフ」、ないものを「無向グラフ」という。
下では有向グラフを考えます。
深さ優先探索(再帰版)
「深さ優先探索」とは、まず枝を進めるだけ進んでみて、行き止まったら引き返して次の枝に行き、そうして求める頂点が見つかるまで進むという方法で探索します。
#頂点 class Vertex end #枝 class Edge def initialize(s, e) @s = s #始点 @e = e #終点 end attr_reader :e end #グラフ class Graph def initialize(vs, h) #hはHash @vs = vs #Array:頂点(要素は Vertex) @es = {} #Hash:枝(Vertex=>Array):Arrayの要素はEdge h.each_key do |k| @es[k] = [] h[k].each {|e| @es[k] << Edge.new(k, e)} end end def get_edges(v) @es[v] #頂点vからのすべての枝(Array)を返す end #goalを見つければtrue, 見つけられなければfalseを返す def find(start, goal) dfs(start, goal, []) end def dfs(v, goal, visited) return true if v == goal return false if visited.include?(v) visited << v return false unless (edges = get_edges(v)) edges.each {|edge| return true if dfs(edge.e, goal, visited)} false end end vs = [1, 2, 3, 4, 5, 6, 7] eh = {1=>[2, 5, 7], 2=>[3, 4], 5=>[4, 6], 6=>[4]} g = Graph.new(vs, eh) vs.each {|v| p g.get_edges(v)}; puts 1.upto(7) {|i| print "#{g.find(5, i)} "}; puts
頂点は vs に入っていて、頂点1〜7まであります。また eh は枝を定義していて、1=>[2, 5, 7] というのは、頂点1 から3本の枝が出ていて、行き先はそれぞれ頂点2, 5, 7 であるという意味です。実行例ではおわかりのように Vertex(頂点)クラスを陽に使っておらず、頂点は Integer で代用(同一視)していますが、もちろん Vertex クラスのオブジェクトを使うこともできます。これは、Ruby がダックタイピング可能であるため、こういう風に楽ができた(?)わけです。
メソッド Graph#find(start, goal) は、頂点 start から goal まで行ければ true、行けなければ false を返します。自分自身には行けます。このメソッド(実質的にはメソッド dfs)が「深さ優先探索」で実装されているわけです。
実行結果。
[#<Edge:*** @s=1, @e=2>, #<Edge:*** @s=1, @e=5>, #<Edge:*** @s=1, @e=7>] [#<Edge:*** @s=2, @e=3>, #<Edge:*** @s=2, @e=4>] nil nil [#<Edge:*** @s=5, @e=4>, #<Edge:*** @s=5, @e=6>] [#<Edge:*** @s=6, @e=4>] nil false false false true true true false
深さ優先探索(ループ版)
class Graph #goalを見つければtrue, 見つけられなければfalseを返す def iter(start, goal) visited = [] q = [start] while !q.empty? v = q.pop return true if v == goal next if visited.include?(v) visited << v next unless (edges = get_edges(v)) edges.each do |edge| next if visited.include?(edge.e) q.push(edge.e) end end false end end
再帰を使わないバージョンです。Graph#find の代わりにメソッド Graph#iter になっています。具体的には、中でスタックを使っています。結果は上とまったく同じ。
幅優先探索
「幅優先探索」とは、頂点から幅を広げるように探索して行く方法です。メソッド Graph#bfs です。
class Graph #goalを見つければtrue, 見つけられなければfalseを返す def bfs(start, goal) visited = [] q = [start] while !q.empty? v = q.shift return true if v == goal next if visited.include?(v) visited << v next unless (edges = get_edges(v)) edges.each do |edge| next if visited.include?(edge.e) q.push(edge.e) end end false end end
これが幅優先探索の実装例です。上の深さ優先探索のループ版と一行しかちがわないのがおわかりでしょうか。q.pop が q.shift になっただけですね。これだけで「幅優先探索」になります。
一般に「幅優先探索」の方が「深さ優先探索」よりもメモリをより多く消費します。それ以外では、グラフの傾向に応じて使い分けることになります。
追記
これ、ライブラリが作れると思ったら、既にあるのですね。自分で車輪の再発明をするのもおもしろそうだが。
Medfreak / Ruby Graph Library (RGL) で遊ぶ
http://gimite.net/gimite/rubymess/graph/
下はグラフを画像化するのに便利そう。
Gvizの目次 - Rubyの世界からGraphvizの世界にこんにちは!