Tests for the implementation of the depth first search algorithm.

dfs.spec.rb

require 'minitest/autorun'
require './depth_first_search_undirected'

describe DFS do

  before do
    graph = {
      :a => [:b, :e],
      :b => [:a],
      :c => [:d, :g, :h],
      :d => [:h, :c],
      :e => [:j, :i],
      :f => [],
      :g => [:c, :h, :k],
      :h => [:d, :l, :c, :g, :k],
      :i => [:e, :j],
      :j => [:e, :i],
      :k => [:g, :h],
      :l => [:h]
    }
    @dfs = DFS.new(graph)
  end

  describe "#dfs" do
    it "should return all reachable vertices from vertex 'a'" do
      assert_equal(@dfs.dfs(:a), [:b, :e, :j, :i])
    end

    it "should return all reachable vertices from vertex 'c'" do
      assert_equal(@dfs.dfs(:c), [:d, :h, :l, :g, :k])
    end

    it "should return all reachable vertices from vertex 'f'" do
      assert_equal(@dfs.dfs(:f), [])
    end

    it "should raise an error if vertex is not defined in graph" do
      assert_raises(RuntimeError) { @dfs.dfs(:foo) }
    end
  end
end

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