You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
39 lines
560 B
Ruby
39 lines
560 B
Ruby
class DFS
|
|
attr_reader :graph
|
|
def initialize(graph, s)
|
|
@graph = graph
|
|
@s = s
|
|
@visited = []
|
|
@edge_to = {}
|
|
|
|
dfs(@graph, @s)
|
|
end
|
|
|
|
def dfs(graph, s)
|
|
@visited << s
|
|
|
|
@graph[s].each do |node|
|
|
next if @visited.include? node
|
|
dfs(graph, node)
|
|
@edge_to[node] = s
|
|
end
|
|
end
|
|
|
|
def path_to?(v)
|
|
@visited.include?(v)
|
|
end
|
|
|
|
def trace_path(v)
|
|
return false unless path_to?(v)
|
|
path = []
|
|
|
|
until v == @s
|
|
v = @edge_to[v]
|
|
path.unshift(v)
|
|
end
|
|
|
|
path.unshift(@s)
|
|
path
|
|
end
|
|
end
|