class DFS
Public Class Methods
new(graph, source)
click to toggle source
# File lib/rbutils/graph/dfs.rb, line 4 def initialize(graph, source) @graph = graph @source = source @visited = [] @edge_to = {} #perform dfs dfs(source) end
Public Instance Methods
dfs(node)
click to toggle source
# File lib/rbutils/graph/dfs.rb, line 14 def dfs(node) #mark node as visited @visited << node #take each adjacent node node.adjacents.each do |adj| next if @visited.include?(adj) #perform dfs dfs(adj) #check edges @edge_to[adj] = node end end
path_to(node)
click to toggle source
# File lib/rbutils/graph/dfs.rb, line 28 def path_to(node) return unless @visited.include?(node) path = [] curr = node #get the paths from the specified node to the #source while(curr != @source) do path.unshift(curr) curr = @edge_to[curr] end path.unshift(@source) end