DS&A

Breadth-First Search

Depth-first search (DFS) is a fundamental algorithm for working with trees, because it gives us a way to “visit” every node in the tree, once each.(1) That’s important, because visiting every node is a subproblem of many other problems on trees.

DFS explores the full depth of one subtree before moving onto the next one. If that’s the order we want to visit the nodes in, or the order doesn’t matter, then DFS is fine; otherwise, we need a different algorithm. We’ll see one in this post.

The tree will be represented using the list-of-children data structure again. For code, see the previous post.

Breadth-first search

Iterative depth-first search keeps track of which nodes to visit using a stack. The stack’s last in, first out behaviour determines what order the nodes are visited in. The breadth-first search (BFS) algorithm has only one difference: it stores the “nodes to visit” in a queue instead.

from collections import deque

def breadth_first_search(root_node, target):
    # create a queue of nodes to visit
    nodes_to_visit = deque([root_node])
    
    while nodes_to_visit:
        # visit the next node
        node = nodes_to_visit.popleft()
        
        if node.value == target:
            # found it!
            return node
        
        # make sure we visit the child nodes
        for child in node.children:
            nodes_to_visit.append(child)
    
    # no more nodes to visit, target wasn't found
    return None

Except for using a queue, the code is identical to iterative DFS, and it works for the same reason — it keeps track of nodes which have been discovered but not yet visited, and the while loop keeps going until there are no more nodes to visit.

DFS vs. BFS

Let’s compare the order that DFS and BFS visit the nodes in. To make sure both algorithms visit every node, we can search for a value which is not in the tree — for example, 11. We can use a print statement to show which node is visited at each step.

As an example, we’ll use the same tree from last time:

The table below shows the results.(2) The nodes are indented to show their depths in the tree; hover over a node to see its children.

Consider the children of node #1; these are nodes #2, #7 and #10. DFS explores the entire subtree of one child before visiting the next child; it visits the nodes in exactly the order they would be written in an outline.

On the other hand, BFS visits all three children before visiting any of their children. When visiting node #2, its children are added to the queue — but nodes #7 and #10 are already in the queue, so these are visited next.

Breadth-first search visits nodes in order of distance from the root node — nodes near to the root are visited earlier, and the deepest nodes are visited last. That is, it searches the full breadth of the tree before trying any deeper nodes.

Footnotes

1. Put another way, DFS is a way to iterate over the nodes of a tree.
2. This comparison uses the recursive implementation of DFS.

• Tags: 
• BFS, queues, trees, search, algorithms