simple_graph.rb

simple_graph.rb

class Graph
  def initialize
    @edges = {}
  end

  def addEdge(src, dst)
    @edges[src] ? (@edges[src] << dst) : (@edges[src] = [dst])
    @edges[dst] ? (@edges[dst] << src) : (@edges[dst] = [src])
    @edges.each {|k, v| v.uniq!}
  end

  def bfs(src)
    return [] unless @edges[src]
    
    seen = {}
    res = []
    stack = []

    stack.push(src)

    while !stack.empty?
      node = stack.pop

      if !seen[node]
        seen[node] = true
        res << node

        @edges[node].each do |adj_node|
          stack.push(adj_node)
        end
      end
    end # while

    res
  end # bfs
end