class BFS
Public Class Methods
new(graph, source)
click to toggle source
# File lib/rbutils/graph/bfs.rb, line 4 def initialize(graph, source) @graph = graph @node = source @visited = [] @edge_to = {} bfs(source) end
Public Instance Methods
bfs(node)
click to toggle source
# File lib/rbutils/graph/bfs.rb, line 13 def bfs(node) #we have to use a queue for BFS queue = [] #initially push the node to the queue queue << node #mark node as visited @visited << node #while there are elements in the wueue, #continue adding from adjacent nodes while queue.any? curr = queue.shift curr.adjacents.each do |adj| next if @visited.include?(adj) queue << adj @visited << adj @edge_to[adj] = curr end end end
path_to(node)
click to toggle source
returns the path to the node after bfs has completed
# File lib/rbutils/graph/bfs.rb, line 36 def path_to(node) return unless @visited.include?(node) path = [] while(node != @node) do path.unshift(node) node = @edge_to[node] end path.unshift(@node) end