Graphs model relationships. A node might represent a city, web page, student, course, or game state. An edge represents a connection between two nodes. Once students see graphs as relationships, traversal becomes much less abstract.
The visited set is essential
Unlike a simple tree, a graph can contain cycles. Without a visited set, traversal can return to the same node again and again.
BFS: level by level
Breadth-first search uses a queue. It explores all nodes one step away, then two steps away, and so on. This makes BFS useful for shortest path problems in unweighted graphs.
DFS: go deep first
Depth-first search uses recursion or a stack. It follows one path as far as possible before backing up. DFS is useful for connected components, path existence, and exploring all possibilities.
Common mistakes
- Marking a node visited too late.
- Forgetting that graph neighbors may appear in any order.
- Using DFS when the problem needs shortest distance by number of edges.
- Assuming every graph is connected.
Practice idea
Draw a six-node graph and trace both BFS and DFS from the same start node. The visited order may differ, but both should avoid revisiting nodes.