幅優先探索→深さ優先探索でした＞＜

バックトラックとかしなくていいので、結構簡単にできた。

# -*- coding: utf-8 -*-
require 'pp'

class Graph
  def initialize(edges)
    @edges = edges
    @nodes = Hash.new{|h,k| h[k] = []}
  end
  
  def add_edge(edge)
    @edges.push edge unless @edges.index(edge)
  end
  
  def add_node(u, v)
    if @edges.index(u).nil?
      @edges.push u
    elsif @edges.index(v).nil?
      @edges.push v
    end
    
    unless @nodes[u].index(v)
      @nodes[u].push v
    end
  end
  
  def breadth_first_search(start, has_approached = [], indent = 0)
    puts " " * indent + start
    has_approached.push start
    @nodes[start].each{|node|
      unless has_approached.include?(node)
        breadth_first_search(node, has_approached, indent+1)
      end
    }
  end
end

g = Graph.new([1, "2", "3"])
g.add_edge("8")
g.add_edge("3")

g.add_node("3", "2")
g.add_node("1", "5")
g.add_node("1", "6")
g.add_node("2", "6")
g.add_node("1", "3")
g.add_node("2", "9")
pp g

g.breadth_first_search("1")

実行結果。それぞれの"層"ごとに結果が出力されているのが分かる。

/tmp% ruby hash_graph.rb
#<Graph:0x8898c
 @edges=[1, "2", "3", "8", "1", "6", "9"],
 @nodes={"1"=>["5", "6", "3"], "2"=>["6", "9"], "3"=>["2"]}>
1
 5
 6
 3
  2
   9

追記

幅優先探索のほう実装したと思っていたら深さ優先のほう実装してたwww。まじ死にたい。。。

再帰を使わない深さ優先探索の実装

再帰使わないとツリーの表示っぽいのはできないんだけど、行けるところを配列で返すみたいなのは再帰を使わないでもできるので。アルゴリズムデザインのp84に載っているアルゴリズムをほぼそのまま使いました。

# -*- coding: utf-8 -*-
require 'pp'

class Graph
  def initialize(edges)
    @edges = edges
    @nodes = Hash.new{|h,k| h[k] = []}
  end
  
  def add_edge(edge)
    @edges.push edge unless @edges.index(edge)
  end
  
  def add_node(u, v)
    if @edges.index(u).nil?
      @edges.push u
    elsif @edges.index(v).nil?
      @edges.push v
    end
    
    unless @nodes[u].index(v)
      @nodes[u].push v
    end
  end

  def dfs(s)
    stack = []
    stack.push s
    explored = []
    while(!stack.empty?)
      u = stack.shift
      if explored.include?(u) == false
        explored.push u
        @nodes[u].each{|v|
          stack.unshift v
        }
      end
    end
    return explored
  end

end

g = Graph.new([1, "2", "3"])
g.add_edge("8")
g.add_edge("3")

g.add_node("3", "2")
g.add_node("1", "5")
g.add_node("1", "6")
g.add_node("5", "8")
g.add_node("2", "6")
g.add_node("1", "3")
g.add_node("2", "9")

pp g
pp g.dfs("1")

でけた。これでis_reacheable?みたいなメソッドは簡単に実装できるなあ。

/tmp% ruby hash_graph.rb
#<Graph:0x88720
 @edges=[1, "2", "3", "8", "1", "6", "5", "9"],
 @nodes={"1"=>["5", "6", "3"], "2"=>["6", "9"], "3"=>["2"], "5"=>["8"]}>
["1", "3", "2", "9", "6", "5", "8"]