Breadth First Search (BFS)

The second important traversal algorithm for graphs is breadth-first search (BFS). The main concept of BFS is that the closest not yet explored node is explored first. This is exactly the opposite strategy compared to DFS.

Explanation of BFS

Let’s execute the BFS algorithm on an example graph as we did for DFS.

In the end result of a BFS execution, all nodes are marked as finished and all distances to the starting node are recorded.

We’ll only discover nodes reachable from the starting vertex, just like we saw for DFS. If we want to explore the whole graph, running further BFS executions from yet undiscovered vertices is needed.

Edge types in BFS

When discussing DFS, we’ll split up the edges into different types: discovery edges, back edges, and redundant edges. The back edges were very useful in discovering cycles. So why are we not doing the same in BFS?

It is not easy to identify back edges in BFS, due to the different node traversal order. When we find an edge that leads “back” to an already discovered or finished node, we cannot be sure that this guarantees a cycle.

For example, check out the following graph where BFS was started from node a, and the current node is d. We find edges leading from d to the finished node c and the discovered node e, but neither of them are part of a cycle. In fact, the graph is acyclic.

Since the detailed edge classifications for BFS are not as useful, they are usually omitted. However, keeping track of which edges are discovery edges can be important.

Application: Shortest paths

We already saw that executing BFS yields us the ...