Graph Traversal: DFS & BFS

📋 Quick Reference

---

🎮 Interactive Visualizer

Watch how DFS and BFS explore graphs differently:

1. Run DFS - see it go deep into one branch first
2. Run BFS - see it explore level by level
3. Compare visit order between algorithms
4. Try on different graph structures (tree, cycle, disconnected)

---

🔧 DFS Implementation

Recursive DFS

JAVA(16 lines)
Code
Loading syntax highlighter...

Iterative DFS (Stack)

JAVA(22 lines)
Code
Loading syntax highlighter...

---

🔧 BFS Implementation

Standard BFS (Queue)

JAVA(19 lines)
Code
Loading syntax highlighter...

BFS with Distance Tracking

JAVA(21 lines)
Code
Loading syntax highlighter...

---

📊 Complexity Analysis

Where V = vertices (nodes), E = edges

Memory Comparison

Tree with depth D and branching factor B:

DFS space: O(D)      - stores path from root
BFS space: O(B^D)    - stores entire level

For wide, shallow trees: DFS uses less memory
For deep, narrow trees: BFS uses less memory

---

✅ When to Use Which

Use DFS When

• Finding any path - not necessarily shortest
• Detecting cycles - track path for back edges
• Topological sort - dependency ordering
• Connected components - explore entire component
• Maze solving - exhaustive exploration
• Memory constrained - lower space for deep graphs

Use BFS When

• Shortest path (unweighted) - guaranteed shortest
• Level-order traversal - process by distance
• Finding nearest - closest node matching condition
• Social network degrees - friends of friends
• Web crawling to depth N - limit crawl depth

---

🧩 Common Patterns

Cycle Detection (Directed Graph)

JAVA(29 lines)
Code
Loading syntax highlighter...

Topological Sort (DFS)

JAVA(25 lines)
Code
Loading syntax highlighter...

Shortest Path (BFS)

JAVA(37 lines)
Code
Loading syntax highlighter...

---

⚠️ Common Pitfalls

1. Forgetting to Mark Visited

JAVA(15 lines)
Code
Loading syntax highlighter...

2. BFS Marking Too Late

JAVA(21 lines)
Code
Loading syntax highlighter...

3. Stack Overflow in Recursive DFS

JAVA(11 lines)
Code
Loading syntax highlighter...

4. Wrong Data Structure for Traversal

JAVA(6 lines)
Code
Loading syntax highlighter...

---

🎤 Interview Tips

"

Use DFS for exhaustive exploration (all paths, cycle detection, topological sort) or when memory is limited. Use BFS when you need the shortest path in unweighted graphs or level-by-level processing.

"

During DFS, if you encounter a visited node that isn't your parent, there's a cycle. For BFS, it's similar - a visited node that isn't the node you came from indicates a cycle.

"

O(V + E) for both DFS and BFS when using adjacency list. Each vertex is visited once (O(V)) and each edge is examined once (O(E)).

"

For unweighted graphs, use BFS - it finds shortest path in O(V + E). For weighted graphs, use Dijkstra (non-negative weights) or Bellman-Ford (with negative weights).

---

📚 Series Navigation

---