## Breadth-First Search

Apr 092018Depth-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.

To implement this in Python, we’ll use the deque class from the collections module.
The queue’s *enqueue* and *poll* operations are implemented using the `append`

and `popleft`

methods.
Here’s the code:

```
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.

#### DFS order

#### BFS order

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

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

## There are no published comments.