Algorithms / Graph Traversal
Least You Need to Know: BFS, DFS, and Connected Components
Breadth-first search explores layer by layer, while depth-first search follows one path deeply before backtracking. Both are core graph tools, and both can be used to discover reachability and connected components.
Least you need to know
- BFS explores vertices in increasing distance by number of edges from the start.
- In an unweighted graph, BFS finds shortest paths measured by edge count.
- DFS naturally uses recursion or an explicit stack.
- To count connected components in an undirected graph, start a traversal from each unvisited vertex.
- A queue is the hallmark data structure of BFS.
Key notation
- BFS — breadth-first search
- DFS — depth-first search
- component — maximal connected piece of an undirected graph
Worked example
- Starting from a source vertex, BFS first visits all neighbors at distance 1.
- Then it visits vertices at distance 2, then distance 3, and so on.
- That is why BFS gives shortest paths in unweighted graphs.
Common mistakes
- Students often swap the queue behavior of BFS with the stack behavior of DFS.
- Students often use DFS when the question specifically asks for the fewest edges in an unweighted graph.
- Students often forget to restart traversal when counting components.
How to recognize it
- If the question says fewest edges in an unweighted graph, think BFS.
- If the question emphasizes recursive exploration or backtracking, DFS is a natural fit.
- If not all vertices are reachable from the first start vertex, components may require repeated restarts.
Next recommended lesson
Continue through this topic with Least You Need to Know: Greedy Choice, Exchange Arguments, and Local Decisions.
Least You Need to Know: Greedy Choice, Exchange Arguments, and Local DecisionsRelated lessons
Keep going with nearby lessons in the same topic.