-
-
Notifications
You must be signed in to change notification settings - Fork 295
/
depth_first_search.rb
53 lines (46 loc) · 1005 Bytes
/
depth_first_search.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# @param [Integer] start
# @param [Integer] target
# @param [Array] adjacency_list
# @return [Array] routes
def dfs(start, target, adjacency_list)
is_visited = Hash.new(false)
parent = {}
stack = [start]
loop do
break if stack.empty?
current_node = stack.pop
is_visited[current_node] = true
return get_path(parent, target) if current_node == target
adjacency_list[current_node].each do |neighbor|
next if is_visited[neighbor]
stack << neighbor
is_visited[neighbor] = true
parent[neighbor] = current_node
end
end
[]
end
# @param [Hash] parent
# @param [Integer] dest
# @return [Array] path
def get_path(parent, dest)
iterator = dest
path = [dest]
while parent.has_key?(iterator)
path << parent[iterator]
iterator = parent[iterator]
end
path.reverse
end
def main
adjacency_list = [
[1, 2], # 0
[0, 3], # 1
[0, 3], # 2
[1, 2, 4], # 3
[3, 5], # 4
[4] # 5
]
p dfs(0, 5, adjacency_list)
end
main