Graph Traversal

Graphs model relationships: social networks connect people, maps connect locations, dependencies connect tasks. This article covers the foundations: how to represent graphs efficiently and how to systematically explore them using Depth-First Search (DFS) and Breadth-First Search (BFS). These traversals are building blocks for shortest paths, cycle detection, topological sorting, and many other algorithms.

📋 At a Glance

Representation	Space	Add Edge	Check Edge	Iterate Neighbors
Adjacency Matrix	O(V²)	O(1)	O(1)	O(V)
Adjacency List	O(V+E)	O(1)	O(degree)	O(degree)
Edge List	O(E)	O(1)	O(E)	O(E)

Traversal	Time	Space	Best For
DFS	O(V+E)	O(V)	Cycle detection, topological sort, path finding
BFS	O(V+E)	O(V)	Shortest path (unweighted), level-order traversal

🎯 What You'll Learn

After reading this article, you will be able to:

Choose the right representation based on graph density and operations
Implement DFS both recursively and iteratively
Apply BFS for shortest path in unweighted graphs
Detect cycles in directed and undirected graphs
Perform topological sort using DFS and Kahn's algorithm
Recognize graph problems disguised as other problems

🔥 Production Story: The Circular Dependency Disaster

A build system managed 500+ microservices with complex dependencies. One day, a developer introduced a circular dependency, and the build hung indefinitely.

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

The problem: No cycle detection. When A depends on B depends on C depends on A, the recursive build never terminates.

The solution:

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

Additional improvement - finding the actual cycle:

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

The lesson: Any system with dependencies is a graph. Cycle detection isn't optional - it's essential for reliability.

🧠 Mental Model: Graph Representations

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

🔬 Deep Dive: Graph Representation

Adjacency List (Most Common)

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

Weighted Graph

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

Generic Graph with Labels

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

Adjacency Matrix

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

When to Use Which

Representation	Best For
Adjacency List	Sparse graphs (E << V²), iterating neighbors
Adjacency Matrix	Dense graphs, checking edge existence
Edge List	Algorithms that iterate all edges (Kruskal's MST)
HashMap-based	Labeled vertices, dynamic graphs

🔬 Deep Dive: Depth-First Search (DFS)

🎮 Try It Yourself

Compare DFS and BFS traversal visually. Watch how DFS explores deeply before backtracking, while BFS explores level by level:

Recursive DFS

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

Iterative DFS

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

DFS with Edge Classification

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

DFS Visualization

TEXT(24 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: Breadth-First Search (BFS)

Basic BFS

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

BFS with Levels

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

BFS vs DFS Comparison

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

🔬 Deep Dive: Cycle Detection

Cycle Detection in Undirected Graph

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

Cycle Detection in Directed Graph

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

🔬 Deep Dive: Topological Sort

DFS-Based Topological Sort

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

Kahn's Algorithm (BFS-Based)

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

Topological Sort Visualization

TEXT(36 lines)
Code
Loading syntax highlighter...

⚠️ Common Mistakes

Mistake 1: Missing Visited Check

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

Mistake 2: Marking Visited at Wrong Time (BFS)

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

Mistake 3: Wrong Parent Check in Undirected Cycle Detection

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

Mistake 4: Forgetting Disconnected Components

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

🐛 Debug This: The Broken Graph Algorithms

These implementations have bugs. Find and fix them:

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

💡 Hint

Look for:

Distance increment in BFS
Order reversal in topological sort
Distinguishing "visited" from "on current path" in cycle detection

✅ Solution

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

Bugs explained:

BFS distance: dist[neighbor] = dist[v] doesn't increment distance. Should be dist[v] + 1.
Topological sort: DFS post-order gives reverse topological order. Need to either reverse the result or add to front of a deque.
Cycle detection: Just checking visited[v] returns true for any visited vertex, not just vertices on the current DFS path. Need separate onStack array to track vertices currently being explored.

💻 Exercises

Exercise 1: Count Connected Components ⭐

Count the number of connected components in an undirected graph.

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

Exercise 2: Bipartite Check ⭐⭐

Check if an undirected graph is bipartite (can be 2-colored).

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

💡 Hint

Use BFS and try to 2-color the graph. If you find an edge between two vertices of the same color, it's not bipartite.

Exercise 3: All Paths Between Two Vertices ⭐⭐⭐

Find all paths from source to destination in a DAG.

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

Exercise 4: Course Schedule II (LeetCode 210) ⭐⭐⭐

Given n courses and prerequisites, return order to finish all courses.

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

Exercise 5: Clone Graph (LeetCode 133) ⭐⭐⭐⭐

Deep copy a graph where each node has value and list of neighbors.

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

🎤 Interview Questions

Question 1: When would you use BFS vs DFS?

Answer:

Use BFS when:	Use DFS when:
Finding shortest path (unweighted)	Detecting cycles
Level-order traversal	Topological sort
Finding connected vertices at distance k	Finding any path (not necessarily shortest)
Peer-to-peer networks	Solving puzzles (maze, sudoku)
Social network friend suggestions	Memory constrained (BFS queue can be huge)

Key insight:

BFS explores "outward" - good for distance-based problems
DFS explores "deep" - good for existence/connectivity problems

Question 2: How do you detect a cycle in an undirected vs directed graph?

Answer:

Undirected Graph:

During DFS, if we visit an already-visited vertex that's not our parent, there's a cycle
Or: Count edges. If edges ≥ vertices, there's a cycle (in connected graph)

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

Directed Graph:

Need to track vertices on current DFS path (not just visited)
Back edge to vertex on current path = cycle

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

Why the difference? In undirected graphs, edge A-B creates both A→B and B→A. We don't want to falsely detect A→B→A as a cycle.

Question 3: Explain topological sort and its applications

Answer:

Definition: Linear ordering of vertices such that for every edge u→v, u comes before v.

Only possible for: Directed Acyclic Graphs (DAGs)

Algorithms:

DFS-based: Reverse post-order of DFS gives topological order
Kahn's (BFS-based): Repeatedly remove vertices with in-degree 0

Applications:

Build systems (compile dependencies)
Course scheduling
Task scheduling
Package managers
Spreadsheet cell evaluation order
Deadlock detection (cycle in wait-for graph)

Question 4: How would you find the shortest path in an unweighted graph?

Answer:

Use BFS. BFS explores vertices in order of their distance from the source.

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

Why BFS works: BFS processes vertices level by level. When we first reach a vertex, it's via the shortest path (fewest edges).

For weighted graphs: Use Dijkstra's algorithm (next article).

Question 5: How do you represent a graph in code?

Answer:

Three main representations:

Adjacency List (most common):

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

Space: O(V + E), Good for: sparse graphs, iterating neighbors

Adjacency Matrix:

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

Space: O(V²), Good for: dense graphs, checking edge existence in O(1)

Edge List:

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

Space: O(E), Good for: algorithms that iterate all edges (Kruskal's)

Choosing representation:

Sparse graph (E << V²): Adjacency list
Dense graph (E ≈ V²): Either works, matrix if need O(1) edge lookup
Need to iterate all edges: Edge list or adjacency list
Dynamic (add/remove vertices): HashMap-based adjacency list

📋 Quick Reference

Graph Terminology

Term	Definition
Vertex (Node)	Point in graph
Edge	Connection between vertices
Directed	Edges have direction (u → v)
Undirected	Edges are bidirectional
Weighted	Edges have values/costs
Path	Sequence of vertices connected by edges
Cycle	Path that starts and ends at same vertex
Connected	Path exists between every pair of vertices
DAG	Directed Acyclic Graph
Degree	Number of edges at a vertex
In-degree	Number of incoming edges (directed)
Out-degree	Number of outgoing edges (directed)

Complexity Summary

Operation	Adjacency List	Adjacency Matrix
Space	O(V + E)	O(V²)
Add vertex	O(1)	O(V²)
Add edge	O(1)	O(1)
Remove edge	O(degree)	O(1)
Check edge	O(degree)	O(1)
Iterate neighbors	O(degree)	O(V)
DFS/BFS	O(V + E)	O(V²)

Code Templates

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

📅 Review Schedule

Day	Focus	Time
Day 1	Read article, implement Graph class	60 min
Day 3	Implement DFS and BFS from scratch	30 min
Day 7	Implement cycle detection and topological sort	30 min
Day 14	Solve 3 LeetCode graph problems	45 min
Day 30	Review and implement clone graph	20 min

🔗 What's Next?

Part 12: Shortest Path Algorithms covers:

Dijkstra's algorithm with priority queue
Bellman-Ford for negative weights
Floyd-Warshall for all pairs
A* heuristic search
Bidirectional search

Key insight preview: BFS finds shortest path by edge count. Dijkstra's finds shortest path by edge weight - a crucial distinction for real-world applications like navigation.

This article is part of the Algorithms Compendium series. For the complete learning path, see Part 0: How to Use This Series.

📋 At a Glance

🎯 What You'll Learn

🔥 Production Story: The Circular Dependency Disaster

🧠 Mental Model: Graph Representations

🔬 Deep Dive: Graph Representation

Adjacency List (Most Common)

Weighted Graph

Generic Graph with Labels

Adjacency Matrix

When to Use Which

🔬 Deep Dive: Depth-First Search (DFS)

🎮 Try It Yourself

Recursive DFS

Iterative DFS

DFS with Edge Classification

DFS Visualization

🔬 Deep Dive: Breadth-First Search (BFS)

Basic BFS

BFS with Levels

BFS vs DFS Comparison

🔬 Deep Dive: Cycle Detection

Cycle Detection in Undirected Graph

Cycle Detection in Directed Graph

🔬 Deep Dive: Topological Sort

DFS-Based Topological Sort

Kahn's Algorithm (BFS-Based)

Topological Sort Visualization

⚠️ Common Mistakes

Mistake 1: Missing Visited Check

Mistake 2: Marking Visited at Wrong Time (BFS)

Mistake 3: Wrong Parent Check in Undirected Cycle Detection

Mistake 4: Forgetting Disconnected Components

🐛 Debug This: The Broken Graph Algorithms

💻 Exercises

Exercise 1: Count Connected Components ⭐

Exercise 2: Bipartite Check ⭐⭐

Exercise 3: All Paths Between Two Vertices ⭐⭐⭐

Exercise 4: Course Schedule II (LeetCode 210) ⭐⭐⭐

Exercise 5: Clone Graph (LeetCode 133) ⭐⭐⭐⭐

🎤 Interview Questions

Question 1: When would you use BFS vs DFS?

Question 2: How do you detect a cycle in an undirected vs directed graph?

Question 3: Explain topological sort and its applications

Question 4: How would you find the shortest path in an unweighted graph?

Question 5: How do you represent a graph in code?

📋 Quick Reference

Graph Terminology

Complexity Summary

Code Templates

📅 Review Schedule

🔗 What's Next?

Tags: