Lesson 11 of 16 · 32:11
Graphs: DFS & BFS
A graph represents objects as vertices and relationships as edges. The hardest step is often modeling: what is a node, what creates an edge, is direction meaningful, and is there a weight? Once that model is explicit, DFS and BFS are systematic ways to explore the reachable structure.
Unlike a rooted tree, a graph can contain cycles and multiple paths to the same vertex. A visited policy is therefore part of correctness. It prevents infinite traversal and repeated work, and its timing affects whether the same vertex enters the frontier more than once.
What you should be able to do after this lesson
- Define vertices and edges from the problem
- Choose a representation from graph density and operations
- Mark visited at the correct discovery moment
The mental model
A graph is a set of states plus legal transitions. The frontier holds discovered work; the visited set prevents cycles and duplicate processing.
Recognize it when: Graph modeling applies to networks, grids, prerequisites, transformations, dependencies, routes, connected components, and any problem that asks what can reach what.
The invariant to say aloud: A state is marked discovered before it enters the frontier, so every vertex is scheduled at most once and every explored edge has a known source.
Learn the ideas one at a time
Concept 1 of 6
Representations
Watch from 3:54 ↗An edge list is compact for iteration, an adjacency matrix gives O(1) edge tests at O(V²) space, and an adjacency list is usually best for sparse traversal.
An edge list is simple when you mainly iterate over edges. An adjacency matrix spends O(V²) space for constant-time edge tests. An adjacency list stores each vertex's neighbors and uses O(V+E) space, making it the usual choice for sparse traversal.
Walk through an example
For edges A-B and A-C, an undirected adjacency list stores B,C under A, A under B, and A under C. Each undirected edge appears twice in neighbor lists.
In an interview
State whether the graph is directed and whether parallel edges or self-loops are possible before constructing the representation.
Concept 2 of 6
Recursive DFS
Watch from 7:49 ↗Mark a node, then recursively explore each unvisited neighbor. The call stack stores the current path and may grow to O(V).
DFS marks a vertex and recursively explores each unvisited neighbor. The recursion stack represents the current path. Marking before recursing is essential: in a cycle A-B-C-A, waiting until after child exploration never reaches a safe completion point.
Walk through an example
Visit A and mark it, then visit B and mark it, then C. When C sees A, A is already marked, so that edge is skipped instead of reopening the cycle.
In an interview
Define whether visited is global for the whole search, local to a path, or represented by colors. Cycle detection sometimes needs more than a single boolean.
Concept 3 of 6
Iterative DFS
Watch from 11:32 ↗Use an explicit stack. Neighbor push order determines visitation order, but reachability does not depend on that order.
A stack replaces recursive frames and avoids recursion-depth limits. Push order controls the deterministic visitation order because the last neighbor pushed leaves first. Correct reachability does not depend on a particular neighbor order unless the problem asks for one.
Walk through an example
To visit alphabetical neighbors B before C, push C first and B second. B sits on top and is processed next.
In an interview
Avoid duplicate work by marking on push or by skipping already visited entries immediately on pop; explain which policy you chose.
Concept 4 of 6
BFS
Watch from 14:18 ↗Use a queue so vertices at distance d are processed before d+1. This yields shortest path length in an unweighted graph.
BFS uses a queue to expand the graph in layers of edge count. In an unweighted graph, every path that reaches a vertex later is at least as long as the first queued discovery, so the first distance assigned is shortest.
Walk through an example
Distance 0 contains the source. Its unseen neighbors receive distance 1, their unseen neighbors distance 2, and the FIFO queue ensures the entire earlier layer is processed first.
In an interview
Use BFS for fewest unweighted edges. Weighted shortest paths require a different priority rule, such as Dijkstra for nonnegative weights.
Concept 5 of 6
Complexity
Watch from 17:27 ↗With adjacency lists, DFS and BFS take O(V+E) time and O(V) auxiliary space. A matrix scan may cost O(V²).
With an adjacency list, each vertex is marked once and each stored edge entry is inspected once, so traversal is O(V+E). The visited set and frontier can hold O(V). An adjacency matrix forces a full row scan per vertex, producing O(V²) work even for sparse graphs.
Walk through an example
A graph with 1,000 vertices and 1,200 edges has a small adjacency list, while its matrix has one million cells. Representation changes the actual traversal work.
In an interview
Count vertices and edges separately and mention that an undirected edge is stored twice without changing the O(E) class.
Concept 6 of 6
Trees as graphs
Watch from 19:35 ↗A tree is connected and acyclic, so a parent reference can replace a general visited set during rooted traversal.
A tree is connected and acyclic, so when traversing away from a chosen root, the parent is the only already-visited neighbor on the current edge. Passing parent can replace a general visited set, provided the input truly is a tree.
Walk through an example
At node B reached from A, skip neighbor A and recurse into every other neighbor. No other back edge exists because the structure is acyclic.
In an interview
Do not remove visited blindly just because the problem uses tree-like language. Verify the connected and acyclic guarantee.
Before you call this lesson done
- Model nodes and directed/undirected edges
- Choose list, matrix, or edge list intentionally
- Define visited timing
- Use BFS only for the distance guarantee it actually provides
