Depth First Search and Breadth First Search (graph search series)

I shall be writing a series of posts on graph search algorithms, starting from this one.

Depth first search and breadth first search are among the simplest of algorithms and are generally used as a basis for implementing more sophisticated searches rather than just to be used as is. These algorithms are used as a way to traverse the nodes of trees or general graphs in a systematic way according to how the nodes are connected.

Depth first search starts from the root node, or simply the start node in a general graph, process the node, take a new neighboring node and repeat. When there are no more new neighboring nodes to take, go back to the node that got you to the current node, take another new node and repeat. If you go back to the root then you have traversed all nodes and the process ends.

If "O" is an unprocessed node, "X" is a processed node and "(X)" is the current node, here's what would happen to this tree:

_____+-------O-------+
 +---O---+       +---O---+
 O       O       O       O

     +------(X)------+
 +---O---+       +---O---+
 O       O       O       O

     +-------X-------+
 +--(X)--+       +---O---+
 O       O       O       O

     +-------X-------+
 +---X---+       +---O---+
(X)      O       O       O

     +-------X-------+
 +--(X)--+       +---O---+
 X       O       O       O

     +-------X-------+
 +---X---+       +---O---+
 X      (X)      O       O

     +-------X-------+
 +--(X)--+       +---O---+
 X       X       O       O

     +------(X)------+
 +---X---+       +---O---+
 X       X       O       O

     +-------X-------+
 +---X---+       +--(X)--+
 X       X       O       O

     +-------X-------+
 +---X---+       +---X---+
 X       X      (X)      O

     +-------X-------+
 +---X---+       +--(X)--+
 X       X       X       O

     +-------X-------+
 +---X---+       +---X---+
 X       X       X      (X)

     +-------X-------+
 +---X---+       +--(X)---+
 X       X       X       X

     +------(X)------+
 +---X---+       +---X---+
 X       X       X       X

     +-------X-------+
 +---X---+       +---X---+
 X       X       X       X

For this to work you need enough memory for remembering the path you have took to get to the current node, assuming that there is a natural order for accessing the next nodes from the current node (that is, you will not revisit the same next node from the current node twice).

Breadth first search starts from the root node, or simply the start node in a general graph, and enqueues it into a queue. Then the next node in the queue is dequeued, the node is processed, all of its neighboring nodes are enqueued into the queue and repeat. If the queue is empty because no processed node has any neighboring nodes to add anymore, all the nodes were traversed and the process ends.

If "O" is an unprocessed node, "X" is a processed node and "(X)" is the current node, here's what would happen to this tree:

_____+-------O-------+
 +---O---+       +---O---+
 O       O       O       O

     +------(X)------+
 +---O---+       +---O---+
 O       O       O       O

     +-------X-------+
 +--(X)--+       +---O---+
 O       O       O       O

     +-------X-------+
 +---X---+       +--(X)--+
 O       O       O       O

     +-------X-------+
 +---X---+       +---X---+
(X)      O       O       O

     +-------X-------+
 +---X---+       +---X---+
 X      (X)      O       O

     +-------X-------+
 +---X---+       +---X---+
 X       X      (X)      O

     +-------X-------+
 +---X---+       +---X---+
 X       X       X      (X)

     +-------X-------+
 +---X---+       +---X---+
 X       X       X       X

For this to work you need enough memory for remembering the queue of nodes that are next to process. The breadth first search is great for working on graphs with infinitely long paths as it does not get stuck traversing the same path but checks all the paths simultaneously as they are gradually traversed. The nodes on the queue are called the "fringe" as they are the edges of this ever widening circle of exploration.

Here is the pseudo code. We shall be using a successor function which gives a list of the next nodes from a given node in order to keep the algorithms as generic as possible.

Iterative version of depth first search:

sub depthFirstSearch(startNode, successorFunction, nodeProcessor):
  stack = [[startNode]]
  while stack is not empty:
    currSiblings = stack.pop()
    currNode = currSiblings.pop()
    if currSiblings is not empty:
      stack.push(currSiblings)

    nodeProcessor(currNode)
    
    nextSiblings = successorFunction(currNode)
    if nextSiblings is not empty:
      stack.push(nextSiblings)

Of course depth first search is naturally recursive so we can do it like this:

sub depthFirstSearch(startNode, successorFunction, nodeProcessor):
  sub _depthFirstSearch(currNode):
    nodeProcessor(currNode)
    for each nextNode in successorFunction(currNode):
      _depthFirstSearch(nextNode)

  _depthFirstSearch(startNode)

Breadth first search is more naturally iterative than recursive:

sub breadthFirstSearch(startNode, successorFunction, nodeProcessor):
  queue = [startNode]
  while queue is not empty:
    currNode = queue.dequeue()

    nodeProcessor(currNode)

    nextNodes = successorFunction(currNode)
    if nextNodes is not empty:
      queue.enqueueAll(nextNodes)

However, this is what it would look like recursively:

sub breadthFirstSearch(startNode, successorFunction, nodeProcessor):
  sub _breadthFirstSearch(queue):
    if queue is not empty:
      currNode = queue.dequeue()

      nodeProcessor(currNode)

      nextNodes = successorFunction(currNode)
      if nextNodes is not empty:
        queue.enqueueAll(nextNodes)

      _breadthFirstSearch(queue)

  _breadthFirstSearch([startNode])