Breath First Traversal

excerpt: In some cases it is appropriate to traverse nodes closer to the start node before the nodes that are farther away. tags: graph-traversal

In some cases it is appropriate to traverse nodes closer to the start node before the nodes that are farther away. The depth first traversal visited nodes far from the start node before it visited closer nodes because it used a stack to process the nodes. If a queue is used instead of stack, the nodes are processed in first-in-first-out order and the nodes closer to the start node are processed first.

The breadth first search gets its name because it visits all of a node’s neighbors before it visits any other nodes. The diagram shows a breadth first traversal with the nodes labeled in the order in which they were traversed.

The traversal starts at the node 0. Its neighbors 1,2 and 3 are added to the queue. The method next processes node 1 and adds its neighbors to the queue. The only neighbor of that node that has not been visited yet is node 4.

The node 2 is removed from the queue and its neighbor 5 is added to the queue. Then the node 3 is removed from the queue and its neighbors 6 and 7 are added to the queue. The nodes closest to the start node are visited before any of the nodes farther away.

 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
  queue = []
  queue.enque(node)
  
  # repeat as long as the stack is not empty
  while !queue.empty?
    # get the next node from the queue
    node = queue.dequeue

    # 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

        # enqueue the node onto the queue
        queue.enque(link.node)
			end
    end
  end
end