Most graph algorithms are based on a traversal of the graph, which is a systematic way of visiting all the vertices and edges in the graph. The two most common types of graph traversals are breadth-first search (BFS) and depth-first search (DFS). Both of these algorithms start at a given vertex and explore the graph to find all the vertices that are reachable from that starting point.
We will first explore breadth-first search. Breadth first search explores the graph in layers, starting from the given vertex and visiting all of its neighbors before moving on to the neighbors of those neighbors. (It spreads out wide or “broadly” from the starting vertex.) It does so by storing a queue of vertices to be explored. At each step, it removes the front item from the queue and explores all of its neighbors that have not yet been explored. Those neighbors are added to the back of the queue to be explored later.
BFS(graph, start):
Queue searchQueue
searchQueue.enqueue(start)
Map parentMap
Map knownMap
knownMap[start] = true
while not searchQueue.isEmpty():
vertex = searchQueue.dequeue()
for each neighbor of vertex:
if not knownMap.contains(neighbor):
knownMap[neighbor] = true
parentMap[neighbor] = vertex
searchQueue.enqueue(neighbor)
Remove the first element from the search queue: 1. Get the list of neighbors of 1. For each neighbor that we do not yet know about, add it to the search queue and remember that we will reach it from 1.
Remove the first element from the search queue: 2. Get the list of neighbors of 2. For each neighbor that we do not yet know about, add it to the search queue and remember that we will reach it from 2.
2 has two neighbors: 0 and 1. We already know about 1, so it is ignored. We add 0 to the search queue. Because we are using a queue, the newly added vertex will be at the back of the line to be explored.
Remove the first element from the search queue: 3. Get the list of neighbors of 3. For each neighbor that we do not yet know about, add it to the search queue and remember that we will reach it from 3.
Remove the first element from the search queue: 5. Get the list of neighbors of 5. For each neighbor that we do not yet know about, add it to the search queue and remember that we will reach it from 5.
Remove the first element from the search queue: 0. Get the list of neighbors of 0. For each neighbor that we do not yet know about, add it to the search queue and remember that we will reach it from 0.
Remove the first element from the search queue: 7. Get the list of neighbors of 7. For each neighbor that we do not yet know about, add it to the search queue and remember that we will reach it from 7.
Remove the first element from the search queue: 4. Get the list of neighbors of 4. For each neighbor that we do not yet know about, add it to the search queue and remember that we will reach it from 4.
Remove the first element from the search queue: 6. Get the list of neighbors of 6. For each neighbor that we do not yet know about, add it to the search queue and remember that we will reach it from 6.
A breadth or depth first search always produces a search tree, which is a subgraph of the original graph that contains all the vertices that were reached during the search and the edges that were used to reach those vertices. Below, this search tree is shown in the original graph and then isolated and restructured to make the tree shape more clear.
Examining the search tree helps to clarify why this is called “breadth-first search”. It explores out in layers, first exploring all the vertices that are one edge away from the starting vertex, then all the vertices that are two edges away, and so on. This means that the path from the starting vertex to any other vertex in the search tree is the shortest path (in terms of number of edges) from the starting vertex to that vertex in the original graph.
Starting from a different vertex in the same graph would produce a different search tree - one that contains the shortest path from that vertex to every other vertex in the search tree.
The animation will load a random graph and start a breadth-first search from vertex 0. Step through the animation. As you do so, note how the Known and Parent tables are updated.
Once you are done exploring from 0, explore from a different starting vertex by entering a Start Vertex number in the input field and clicking on the Run BFS button.
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
The final results of this process can be represented as a full Graph object that contains all the vertices and edges in the search tree. Or, as shown in the animation, we can simply keep track of the parent of each vertex and use that as the search tree representation. With it , we can find the path from the starting vertex to any other vertex in the search tree by following the parent mappings back to the starting vertex. We will know that we have reached the starting vertex when we encounter a vertex that does not have a parent.
For example, consider the parent mapping below (turned horizontal for readability). We can see that vertex 0 was the starting point of the search since it has no parent. To determine the path to vertex 7, we can see that we reach it from vertex 3, which we reach from vertex 1, which we reach from vertex 0. So the path from vertex 0 to vertex 7 is 0 -> 1 -> 3 -> 7.
