Searching a Graph: BFS and DFS
There are two classic ways to explore a graph from a starting node.
- Breadth-first search (BFS) visits all neighbours first, then their neighbours, spreading out in rings. It uses a queue. Because it explores nearest nodes first, it finds the shortest path (fewest edges).
- Depth-first search (DFS) goes as deep as it can along one path before backing up. It uses a stack (or recursion). It suits "is there any path?" and exploring everything.
Both keep a visited set so they never loop forever in a graph that has cycles. Both cost O(nodes + edges).
Examplepython
Quick check
Which search finds the path with the fewest edges?
Your turn: write the code
Use BFS to find the fewest steps (edges) from 'A' to 'F' and print the number.
Finish the quick check (and any code exercise) to complete this lesson, or mark it done yourself.
Tip: use the left and right arrow keys to move between lessons.