breadth-first search, BFS

Queue_bfs.rb

# O(|V|+|E|)
graph = Hash.new

graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

queue = [graph]

def is_person_seller name
  name[-1] == "m" unless name.nil?
end

def search graph, name
searched = []
queue = graph[name]
puts "QUEUE FROM EACH #{queue}"
until queue.empty?
  q = queue.shift
    unless searched.include? q
      if is_person_seller(q)
        puts "#{q} is a mango seller in #{name}"
      else
        puts "NAME FROM EACH #{q}"
        queue += graph[q] unless graph[q].empty?
        searched << q
      end
    end
  end

end

search(graph, "you")