# Depth First Search

Category:

The graph is given.

Graph as a hash:

```
graph = {
0 => [1,9],
1 => [0,8],
2 => [3],
3 => [2,4,5,7],
4 => [3],
5 => [3,6],
6 => [5,7],
7 => [3,6,11,10,8],
8 => [1,7,9],
9 => [0,8],
10 => [7,11],
11 => [7,10],
12 => [],
}
```

Algorithm code with a loop instead of recursion

```
def dfs(graph, start_node)
current_node = start_node
stack = [start_node]
visited = [start_node]
loop do
p "stack: #{stack}"
p "visited: #{visited}"
unvisited_neighbour = graph[current_node].find do |node|
!visited.include?(node)
end
if unvisited_neighbour
current_node = unvisited_neighbour
visited << current_node
stack << current_node
next
else
stack.pop
current_node = stack.last
break unless current_node
end
end
end
dfs(graph, 0)
```