Depth First Traversal

tags: graph-traversal depth-first-search implicit-graph

Depth first search is a type of graph traversal that begins at a given vertex and recursively explores its neighbors. The time complexity is O(V+E), where V is the number of vertices and E is the number of edges in the graph.

The main application of DFS is to discover all the reachable nodes starting from a given vertex of a graph. DFS is a basic building block for several algorithms such as the detection of biconnected components, topological sort etc.

Recursive Implementation

The node and link class encapsulates the functionality of the Node and Link abstrations in a graph.

1
2
3
4
5
6
7

class Node
  attr_accessor :name, :links
end

class Link
  attr_accessor :cost, :node
end

In depth first traversal the current node is first processed. Then the node’s links are recursively processed.

1
2
3
4
5
6
7

def traverse
  # process node here
  # process each link of the node now
  for link in links
    link.node.traverse
  end
end

If the graph contains a cycle, the traverse method will loop forever. There must be a way to tell if a node has been visited before. Add a visited property to the node class.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def traverse
  # process node here
  
  # mark the current node as visited
  visited[node] = true
  
  for link in links
    if !visited[link.node]
      link.node.traverse
    end
  end 
end

Now the current node is marked as visited by setting the visited array to true. Then the node’s links can be processed in the loop. If the node has not been visited before, it is processed in the recursive call.

Alternative Implementation

1
2
3
4
5
6
7
8
9

def dfs(graph, node, visited)
  visited[node] = true
  
  for neighbor in graph[node]
    if !visited[node]
      dfs(graph, neighbor, visited)
    end
  end
end

The disadvantage of the recursive implementation is that it may lead to very deep levels of recursion. If the number of nodes is large, it can exhaust the program’s stack space and crash the program.

Iterative Implementation

Iterative version of the program can avoid this problem. A stack is used to keep track of the state.

 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

def traverse(node)
  # visit the node
  # mark the node as visited
  visited[node] = true
  
  # create a stack and put the start node in it
  stack = []
  stack.push(node)
  
  # repeat as long as the stack is not empty
  while !stack.empty?
    # get the next node from the stack
    node = stack.pop
    
    # process the node's links
    for link in node.links
      # Use the node only if it has not
      # been visited yet
      if !visited[link.node]
        # mark the node as visited
        visited[link.node] = true
        
        # push the node onto the stack
        stack.push(link.node)
			end
    end
  end
end

The start node is first visited and it is pushed onto a stack. Then, as long as the stack is not empty, the next node is retrieved from the stack and it is processed. If a link’s destination node has not been visited, it is marked as visited and added to the stack for later processing.

The graph is traversed in depth-first order. Because the stack returns items in last-in-first-out order, the traversal method moves away from the start node before it gets back to processing that node’s closer neighbors. The traversal visits nodes far away from the start node before it visits all the ones that are closer to the start node, this is called a depth-first traversal.

Alternative Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def dfs(graph, start, visited)
  visited[start] = true
  stack = [start]
  
  while !stack.empty?
    node = stack.pop
    for neighbor in graph[node]
      if !visited[neighbor]
        visited[neighbor] = true
        visited.append(neighbor)
      end
    end
  end
end

Implicit Graph

A grid of dimension i x j is given. Cells that can be visited is marked by the character ‘.’ and cells that cannot be visited is marked by ‘#’. All the neighbor cells of a given cell must be visited. The cells in the boundary have fewer neighbors. The grid itself can be used to mark the visited cells with ‘.’. The recursive traversal is shown below.

 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

def grid_traversal(grid, i, j)
  AVAILABLE = '.'
  NOT_AVAILABLE = '#'
  
  height = grid.size
  width = grid[0].size
  stack = [[i, j]]
  grid[i][j] = NOT_AVAILABLE
  
  while !stack.empty?
    neighbor_i, neighbor_j = stack.pop

    for next_i, next_j in [[neighbor_i + 1, neighbor_j],
                           [neighbor_i, neighbor_j+1],
                           [neighbor_i - 1, neighbor_j],
                           [neighbor_i, neighbor_j - 1]]

      if (0 <= next_i < height and 0 <= next_j < width
          and grid[next_i][next_j] == AVAILABLE)
          
          grid[next_i][next_j] = NOT_AVAILABLE
          stack.append([next_i, next_j]) 
      end
    end
  end
end