Class: BreadthFirstSearch

Inherits:
SearchAlgorithm show all
Defined in:
lib/usearchtree/breadth.rb

Instance Attribute Summary

Attributes inherited from SearchAlgorithm

#goal, #history, #space, #start, #traversal, #tree

Instance Method Summary collapse

Methods inherited from SearchAlgorithm

#cost, #initialize, #path

Constructor Details

This class inherits a constructor from SearchAlgorithm

Instance Method Details

#search ⇒ Object 



2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
# File 'lib/usearchtree/breadth.rb', line 2

def search
    @list = [@start]
    until @list.empty?
        @history << @list.clone
        parent = @list.shift
        @traversal << parent
        @cache[parent.key] = parent
        if parent == @goal
            return
        end
        parent.edges.each do |edge|
            child = edge.node
            if @cache and not @cache.has_key?(child.key)
                @cache[child.key] = child
                @tree[child] = parent
                @list << child
            end
        end
    end
end