Graphs
Curriculum
Master graph algorithms through traversal patterns, connectivity analysis, and systematic exploration of relationships.
What This Category Is Really About
Nodes (vertices) connected by edges. Models networks, dependencies, relationships. Most general data structure—trees are special graphs.
DFS and BFS are fundamental. Explore all reachable nodes systematically. Handle cycles, multiple components, directed vs undirected.
Which nodes are reachable from which? Connected components, strongly connected components, bridges, articulation points.
Finding paths between nodes. Shortest path algorithms: BFS (unweighted), Dijkstra (weighted), Bellman-Ford (negative weights).
Mental Model & Invariants
Graphs are networks of relationships explored through systematic traversal.
"Mark nodes as visited to avoid cycles. Track state (distance, parent, color) to extract information during traversal."
Break this, and you get infinite loops or missed nodes.
Visited Invariant
Mark nodes as visited before processing. Never revisit. Prevents cycles and ensures termination.
Path Invariant
Track parent pointers during traversal. Reconstruct path by backtracking from target to source.
Distance Invariant
BFS discovers nodes in order of distance. First visit to a node is shortest path (unweighted).
Choose Your Traversal
DFS for paths, cycles, topological sort. BFS for shortest paths, level-by-level. Both explore all reachable nodes.
When to Think "Graphs"
sensorsStrong Signals
Network of connections (social, computer, roads)
Dependencies between entities
Shortest path between points
Reachability questions
Cycle detection needed
Connected components
ruleProblem Signals
Many-to-many relationships
Traversal order matters
Need to explore all possibilities
Optimization over network structure
Core Patterns You Must Master
DFS (Depth-First Search)
Explore as far as possible before backtracking. Stack-based (recursive or explicit).
Visit node, mark visited, recurse on unvisited neighbors.
BFS (Breadth-First Search)
Explore level by level. Queue-based. Shortest path in unweighted graphs.
Process nodes in order of distance from source.
Connected Components
Find groups of connected nodes. Run DFS/BFS from each unvisited node.
Each component explored completely before moving to next.
Cycle Detection
Detect cycles in directed/undirected graphs. DFS with color states.
Back edge indicates cycle. Track visiting vs visited.
Topological Sort
Linear ordering of DAG nodes. Dependencies before dependents.
Node added to result after all descendants processed.
Shortest Path
BFS (unweighted), Dijkstra (weighted), Bellman-Ford (negative weights).
Relaxation: update distance if shorter path found.
How to Learn This Category
Master DFS and BFS First
Implement both from scratch. Understand when to use each. Practice on simple graphs. Trace execution by hand.
Learn Graph Representations
Adjacency list vs adjacency matrix. Understand tradeoffs. Practice converting between representations.
Handle Visited State Correctly
Mark nodes visited before processing. Understand difference between visiting and visited. Prevent infinite loops.
Practice Cycle Detection
Detect cycles in directed and undirected graphs. Understand back edges, cross edges, forward edges.
Master Topological Sort
Understand DAG properties. Implement using DFS post-order. Recognize dependency problems.
Learn Shortest Path Algorithms
BFS for unweighted. Dijkstra for weighted positive. Bellman-Ford for negative weights. Understand when each applies.
Canonical Problem List
auto_awesome_motionFoundation
Number of Islands
Count connected components in 2D grid. DFS or BFS.
Clone Graph
Deep copy graph. Track visited nodes with hashmap.
Course Schedule
Detect cycle in directed graph. Topological sort.
Pacific Atlantic Water Flow
DFS/BFS from boundaries. Track reachability.
Flood Fill
DFS/BFS to change connected region. Classic traversal.
auto_awesome_motionIntermediate
Course Schedule II
Return topological ordering. DFS post-order or Kahn's algorithm.
Surrounded Regions
Capture regions not connected to boundary. DFS from edges.
Graph Valid Tree
Check if graph is tree: connected + no cycles.
Number of Connected Components
Count components in undirected graph. Union-Find or DFS.
Shortest Path in Binary Matrix
BFS for shortest path. 8-directional movement.
Rotting Oranges
Multi-source BFS. Track time for all to rot.
auto_awesome_motionAdvanced
Word Ladder
Shortest transformation sequence. BFS on word graph.
Network Delay Time
Dijkstra's algorithm. Shortest path in weighted graph.
Critical Connections in Network
Find bridges. Tarjan's algorithm with low-link values.
Alien Dictionary
Topological sort from character ordering. Build graph from constraints.
Common Mistakes
Not Marking Nodes as Visited
Infinite loops in cyclic graphs. Revisiting same nodes repeatedly.
Mark node as visited immediately when discovered, before processing neighbors.
Confusing Directed vs Undirected
Wrong edge interpretation. Bidirectional when should be unidirectional.
Clarify graph type upfront. In undirected, add edges both ways. In directed, respect edge direction.
Wrong Traversal Choice
Using DFS when BFS needed for shortest path. Or vice versa.
BFS for shortest path (unweighted), level-order. DFS for paths, cycles, topological sort.
Not Handling Disconnected Components
Only exploring from one starting node. Missing entire components.
Loop through all nodes. Start traversal from each unvisited node.
Incorrect Cycle Detection
Marking visited too early/late. Not distinguishing visiting vs visited.
Use three states: unvisited, visiting (in current path), visited (fully processed).
Interview Guidance
What they test
- →DFS vs BFS selection
- →Visited state management
- →Handling disconnected components
- →Graph representation choice
Strategy
Draw the graph. Clarify directed vs undirected. Ask about disconnected components. Choose traversal based on problem requirements. Explain visited tracking.
The Verbal Template
"Is this directed or undirected? Weighted or unweighted? Can there be cycles?"
"I'll use adjacency list for sparse graphs. Allows efficient neighbor iteration."
"I'll use [DFS/BFS] because [reason: shortest path / cycle detection / etc]."
"I'll track visited nodes with a set/array. Mark visited when discovered to prevent loops."
When You've Mastered It
Implement DFS and BFS instantly
Choose correct traversal for problem
Handle visited state without bugs
Detect cycles reliably
Implement topological sort
Recognize graph problems immediately
What This Unlocks Next
Advanced Shortest Path
Dijkstra, Bellman-Ford, Floyd-Warshall. A* search. Handling negative weights and cycles.
Minimum Spanning Trees
Kruskal's and Prim's algorithms. Union-Find data structure. Network design problems.
Network Flow
Max flow, min cut. Ford-Fulkerson, Edmonds-Karp. Bipartite matching.
Advanced Graph Algorithms
Strongly connected components (Tarjan, Kosaraju). Bridges and articulation points. Eulerian paths.