Graph Traversal Methods
🌉 What Is Graph Traversal?
Imagine you’re exploring a new city.
You start from one place and slowly move to nearby places.
As you walk, you keep track of where you’ve already been so you don’t repeat the same street again and again.
Graph traversal works just like that.
Graph Traversal means visiting every reachable vertex in a graph, step by step, in a systematic way.
It helps us explore the graph completely, just like exploring a map.
🗺️ Why Do We Traverse a Graph?
Graph traversal is used when we need to:
- find if a path exists between two nodes
- check if the graph is connected
- solve puzzles like mazes
- analyze networks (computers, roads, social connections)
- build algorithms like shortest path, spanning tree, etc.
Without traversal, a graph is just a drawing. Traversal brings it to life.
🎢 Two Popular Traversal Methods
There are two classic ways to explore a graph:
- Depth First Search (DFS)
- Breadth First Search (BFS)
Think of them as two different ways of walking through a city.
🔍 1. Depth First Search (DFS)
DFS is like being an adventurous traveler.
You walk as far as possible down one path.
If you reach a dead end, you come back and try another path.
You dive deep first, then explore sideways.
✏️ Simple DFS Diagram
Let’s use this small graph:
A
/ \
B C
/ \
D EDFS starting from A would follow a path like:
A → B → D → (back) → E → (back) → CIt explores deep into B before touching C.
🚶♂️ 2. Breadth First Search (BFS)
BFS is like exploring level by level.
First, you look at all places directly connected to you.
Then you move one step further out.
It’s like waves spreading from the starting point.
✏️ Simple BFS Diagram (same graph)
Traversal from A:
A → B → C → D → EYou first visit all neighbors of A, then neighbors of B and C.
📘 Side-by-Side Comparison
| Feature | DFS | BFS |
|---|---|---|
| Style | Go deep first | Explore layer by layer |
| Uses | Maze solving, pathfinding in deep graphs | Shortest path in unweighted graphs |
| Storage | Uses stack (explicit or recursion) | Uses queue |
| Looks like | Exploring one long tunnel | Expanding in circles |
✨ Why Traversal Needs “Visited” Marking
When you explore a city, you remember where you’ve already been.
Otherwise, you might keep walking in circles.
Graphs can have cycles, like:
A → B → C → ASo we keep a visited list to avoid infinite loops.
🧠 A Friendly Analogy
Think of a graph traversal like meeting people in a huge community event.
- DFS: You stick to one person, follow them to their friends, and then their friends’ friends… until there’s no one new.
- BFS: You first meet all people standing near you, then approach the next circle, then the next.
Both ways help you meet everyone — but the order feels very different.
🖍️ Putting It All Together (Diagram)
Here’s a combined visual idea of DFS vs BFS:
A
/ \
B C
/ \
D E
DFS (from A): A → B → D → E → C
BFS (from A): A → B → C → D → EAbout the Author
