Class: MiniGraph::Core::Search::DFS

Inherits:
Base
  • Object
show all
Defined in:
lib/mini_graph/core/search.rb

Overview

Depth-First Search

Instance Attribute Summary

Attributes inherited from Base

#graph, #vertex_index

Instance Method Summary collapse

Methods inherited from Base

#each, #initialize

Constructor Details

This class inherits a constructor from MiniGraph::Core::Search::Base

Instance Method Details

#visit(index, visited = Array.new(graph.size, false)) {|index| ... } ⇒ Object

Yields:

  • (index) 


37
38
39
40
41
42
43
44
 
# File 'lib/mini_graph/core/search.rb', line 37

def visit(index, visited=Array.new(graph.size, false), &block)
  visited[index] = true
  yield index

  graph.adjacent_vertices(index).each do |vi|
    visit(vi, visited, &block) unless visited[vi]
  end
end