Breadth-first and depth-first search

The previous example is historically notable, but a more common desire in graph traversal is to find a node within the graph starting from some other node. There are several ways of addressing this challenge. For unweighted graphs such as our Twitter follow graph, the most common are breadth first and depth first search.

Breadth first search starts with a particular vertex and then searches each of its neighbors for the target vertex. If the vertex isn't found, it searches each of the neighbor's neighbors in turn, until either the vertex is found or the entire graph has been traversed.

The following diagram shows the order in which the vertices are traversed, beginning at the top and working down in tiers, from left to right:

Loom contains a variety of traversal algorithms in the loom.alg namespace. Let's perform breadth first search on the same Twitter followers graph we have been studying, which is repeated for convenience:

Breadth-first traversal is provided...