Breadth First Search (BFS)
Explore how breadth first search BFS works as a graph traversal algorithm that explores nodes closest from the start vertex first. Learn to use BFS to compute shortest paths by tracking parent nodes and understand the differences in edge classifications compared to DFS.
We'll cover the following...
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 ...
Edge types in BFS
When discussing DFS, ...