Breadth First Search

Breadth_First_Search.rb

require '../lib/Queue'

        frontier = Queue.new
        
# set up the adjacency list that defines the graph        

        neighbors = {}
        neighbors = {:a => [:b,:f], :b => [:c,:d], :c => [:e], :d =>[:e], :e =>[:c,:d], 
                                        :f => [:a,:g,:h,:i], :g => [:f], :h => [:f], :i => [:f] }
        parent = {}
        visited = []

        
# :a is the source node for BFS search. Put :a into the frontier queue
        parent[:a] = nil
        frontier.enqueue(:a)


        while !frontier.empty? do
                frontier.each do |node| 
                        neighbors[node].each do |neighbor|
                                if frontier.include?(neighbor) || visited.include?(neighbor) 
                                        next
                                else
                                        frontier.enqueue(neighbor)
                                        parent[neighbor] = node
                                end
                        end
                end
                visited << frontier.dequeue

        end