深さ優先探索と幅優先探索

木構造のコレを元に探索コード書いてみた。

Tree#search

深さ優先探索。

      user     system      total        real
depth-first search:
  0.000000   0.000000   0.000000 (  0.000058)
  0.000000   0.000000   0.000000 (  0.000033)

Tree#search_b

幅優先探索。

Beadth first search:
  0.000000   0.000000   0.000000 (  0.000104)
  0.000000   0.000000   0.000000 (  0.000078)

実行時間

　最も深いノード*1を探索対象にしたので、幅優先探索よりも深さ優先探索の実行時間が短ければ正しい動作のはず。

コード

require "benchmark"

class Tree
    attr_reader :root, :childs, :data
    def initialize(data, root=nil)
        @root = root
        @data = data
        @childs = []
    end
    def addNode(data)
        @childs << Tree.new(data,self)
    end
    def addNodes(ary_data)
        ary_data.each do |l|
            addNode(l)
        end
    end
    def search(pattern)
        #depth-first search
        if /#{pattern}/ =~ @data then return self end
        if @childs.length != 0 then
            @childs.each do |node|
                result = node.search(pattern)
                if result then return result end
            end
        end
        return nil
    end
    def search_b(pattern, queue=[])
        #Beadth first search
        if queue.length == 0 then queue.unshift(self) end
        node = queue.pop
        if /#{pattern}/ =~ node.data then return node
        else
            node.childs.each do |child|
                queue.unshift(child)
            end
        end
        if queue.length == 0 then return nil end
        search_b(pattern, queue)
    end
end

tree = Tree.new("Animal")
tree.addNodes(["Human","Cat","Dog"])
tree.childs[0].addNodes(["Men","Women"])
tree.childs[0].childs[0].addNodes(["Tanaka","Satou"])
tree.childs[1].addNodes(["Mike",'Shamu','Kuro'])
tree.childs[2].addNodes(['Golden','Shiba'])

result = nil

# stopwatch
puts Benchmark::CAPTION
puts "Beadth first search:"
puts Benchmark.measure {
    result = tree.search_b("Tanaka")
}
puts Benchmark.measure {
    result = tree.search_b("Tanaka")
}
puts "depth-first search:"
puts Benchmark.measure {
    result = tree.search("Tanaka")
}
puts Benchmark.measure {
    result = tree.search("Tanaka")
}

p result.data

*1:さらに左端