Class: MiniGraph::Core::Search::BFS

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

Overview

Breadth-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), &block) ⇒ Object 



52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
# File 'lib/mini_graph/core/search.rb', line 52

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

  queue.push(index)

  while !queue.empty?
    next_index = queue.shift
    yield next_index

    graph.adjacent_vertices(next_index).each do |vi|
      unless visited[vi]
        visited[vi] = true
        queue.push(vi)
      end
    end
  end
end