1.9 Graphs

Deep Dive: Graph Traversal Visualized

Beginner tip: A graph is a set of dots (nodes) connected by lines (edges). Think of a social network: each person is a node, friendships are edges. Trees are special graphs with no loops. Most graph problems boil down to: "Visit every reachable node" (DFS/BFS), "Find the shortest path" (BFS), or "Detect a loop" (DFS with coloring).

BFS vs DFS on Number of Islands

Grid (1=land, 0=water):

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

DFS (island 1): Start at (0,0). Go deep first:

(0,0) -> (0,1) -> (1,1) -> (1,0) -> backtrack, backtrack...
Marked: all four '1's in top-left as visited. Island count = 1.

BFS (island 1): Start at (0,0). Go wide first:

Queue: [(0,0)]
  Process (0,0) -> enqueue neighbors (0,1), (1,0)
Queue: [(0,1), (1,0)]
  Process (0,1) -> enqueue (1,1)
  Process (1,0) -> (1,1) already queued
Queue: [(1,1)]
  Process (1,1) -> no new neighbors
Island count = 1. Then find (2,2) -> island 2. Then (3,3) -> island 3.

Both give the same answer (3 islands). BFS finds shortest paths; DFS uses less memory on narrow graphs.

Cycle Detection: The 3-State Trick

For directed graphs (Course Schedule), use 3 states:

State 0 = UNVISITED (white)
State 1 = VISITING  (gray)  -- currently in recursion stack
State 2 = VISITED   (black) -- fully processed

If you reach a GRAY node -> CYCLE! (you looped back to an ancestor)
If you reach a BLACK node -> safe (already processed, no cycle through here)

BFS = Shortest Path (Unweighted)

Why BFS gives shortest path but DFS does not:

BFS explores ALL nodes at distance 1, then ALL at distance 2, etc.
The first time BFS reaches a node, that IS the shortest path.

DFS might reach a node via a long winding path first.

---

Quick Reference (Cheat Sheet)

Before You Start -- How to Think About Graphs

Why Graphs Exist

Need: Model arbitrary relationships (friends, roads, dependencies). Key insight: Trees are special graphs (connected, no cycles). Graphs are the general case.

The Graph Mindset

Every graph problem is about TRAVERSAL. The question is: BFS or DFS? And what do I track during traversal?

Step 1: How Is the Graph Given?

Before solving, figure out the representation:

Given As	Convert To	Example
Edge list [[0,1],[1,2]]	Adjacency list	{0:[1], 1:[0,2], 2:[1]}
Adjacency matrix	Usually use as-is	matrix[i][j] == 1 means edge
Grid/Matrix	Implicit graph	Neighbors = 4 directions (up/down/left/right)
Prerequisites [[1,0]]	Directed adjacency list	{0:[1]} means 0->1

Step 2: BFS or DFS?

Use BFS When...	Use DFS When...
Shortest path (unweighted)	Explore all paths
Level-by-level processing	Deep dive first
"Minimum steps to reach"	"Does a path exist?"
Multi-source spread (rotten oranges)	Connected components

Step 3: What Extra State Do I Track?

- VISITED set -> Always. Prevents infinite loops in cycles.
- DISTANCE / LEVEL -> For shortest path / level-order
- PARENT map -> To reconstruct the actual path
- COLOR / STATE -> For cycle detection (white/gray/black)
- COMPONENT ID -> For counting connected components

Graph Problem Categories

Category	Signal	Technique
Traversal	"Visit all", "connected"	BFS or DFS
Shortest Path	"Minimum steps", "closest"	BFS (unweighted), Dijkstra (weighted)
Cycle Detection	"Is valid tree?", "redundant"	DFS (back edge) or Union-Find
Topological Sort	"Prerequisites", "ordering"	Kahn's BFS or DFS
Connected Components	"Number of islands", "groups"	DFS/BFS or Union-Find

Common Mistakes

• Forgetting the visited set -> infinite loop on cycles
• For grids: forgetting to mark visited BEFORE adding to queue (causes duplicates)
• Directed vs undirected: adding edges in both directions when it should be one-way
• Topological sort: forgetting to check for cycles (if cycle exists, no valid ordering)

Problems

#	Problem	Difficulty	Pattern	Status
1	Number of Islands	Medium	DFS/BFS flood fill	[ ]
2	Clone Graph	Medium	BFS + HashMap	[ ]
3	Course Schedule I & II	Medium	Topological Sort	[ ]
4	Pacific Atlantic Water Flow	Medium	Multi-source BFS	[ ]
5	Graph Valid Tree	Medium	Union-Find / DFS	[ ]
6	Number of Connected Components	Medium	DFS / Union-Find	[ ]
7	Word Ladder	Hard	BFS shortest path	[ ]

Notes