グラフと探索(Ruby)

アルゴリズムを学ぼう

アルゴリズムを学ぼう

いま上の本を読んでいるのですが、コード例が Java なのですね。なので、勉強のため Ruby で書いてみました。
グラフと探索についてです。

まずグラフですが、本書での定義を書いておきます。

グラフ(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の世界にこんにちは!