DFS as a class

DFS.rb

class DFS

  attr_reader :adj_list, :parent

  def initialize(adj_list={})
    @adj_list = adj_list
    @parent = {}
  end

  def dfs_run!(starting_node)
    @parent[starting_node] = :none
    dfs_visit!(starting_node, @adj_list[starting_node])
  end

private

  def dfs_visit!(node, adj_list_of_node)
    adj_list_of_node.each do |vertex|
      if !(parent.has_key?(vertex)) #if vertex is NOT in parent hash, it has not been explored
        parent[vertex] = node
        dfs_visit!(vertex,@adj_list[vertex])
      end
    end
  end

end

a DFS object should be initialized with the adjacency list defining the graph to be traversed as a hash of the form
adj = { :a => [:b,:c], :b => [:a], :c => [:a]}.

The hash adj shows all nodes and symbols, with the key,value pairs as the node and an array of all nodes reachable in one step.

When dfs_run! message is sent to the object, the parent hash is computed and saved as an instance variable.