An implementation of the depth first search algorithm for undirected graphs.

dfs.rb

class DFS

  def initialize(graph={})
    @graph = graph
    @visited = {}
  end

  # This implementation of depth-first search visits
  # only the portion of the graph reachable from the
  # starting vertex
  # Input: A vertex element of the graph
  # Output: All reachable vertices from vertex
  def dfs(vertex)
    raise RuntimeError if @graph[vertex].nil?
    @visited = {}
    explore(@graph[vertex], vertex)
    return @visited.keys - [vertex]
  end

  private

  # Find all reachable vertices from a particular vertex
  def explore(graph_of_vertex, current_vertex)
    @visited[current_vertex] = true
    graph_of_vertex.each do |vertex|
      if not @visited[vertex]
        explore(@graph[vertex], vertex)
      end
    end
  end
end

See full blogpost here: https://medium.com/@diegocasmo/depth-first-search-in-undirected-graphs-8d563ef4004e#.mlsfh1b0e