Graph Foundations

10 concept walkthroughs, each with a worked explanation and an interactive visualization, before you start solving problems in this area.

What Is a Graph?

A graph is the most general way to connect data: a set of NODES (also called vertices) joined by EDGES. That's the entire definition: no root, no parent/child, no rules about shape. Any node can connect to any other.

# a graph is just two sets:
nodes = {A, B, C, D, E, F}
edges = {(A,B), (A,D), (B,E), (C,F)}

# a tree is a graph that promises:
#   no cycles, and exactly n-1 edges

Six friends, one rumor: your first graph

Meet a friend group: Aisha (A), Ben (B), Chloe (C), Dev (D), Esha (E), Farid (F). Aisha is friends with Ben and with Dev. Ben is friends with Esha. Chloe is friends with Farid. Draw each person as a dot and each friendship as a line between two dots, and you have built a graph: 6 NODES, 4 EDGES. That is the entire construction, there is no step two.

Now use it. Aisha hears a rumor and tells her friends. Trace it along the lines with a finger: A tells B and D. B tells E. And then it stops. Nobody who has heard the rumor is friends with C or F. The drawing just answered a real question ('who eventually hears?') purely through its connections. Every graph algorithm you will learn in this track is a disciplined version of that finger-trace.

A tree is a graph that signed a contract

You spent a whole track on trees, and a tree IS a graph, one that signed a three-clause contract: no cycles, exactly one path between any two nodes, and everything hanging together off one root. General graphs tear that contract up. Add a single friendship D–E to our network and you get a CYCLE: A → B → E → D → back to A. Now there are TWO routes from A to E (via B, or via D), and walking without care means walking in circles forever.

The third clause breaks too: nothing forces a graph to be one piece. C and F float apart, unreachable no matter how long you walk from A. Cycles, multiple routes, disconnection: these three new freedoms are exactly what the next nine concepts teach you to handle. Everything else you know from trees transfers unchanged.

The whole structure is two lines of data

In code, a graph needs no clever object, it is literally two collections. Pause on that: the structure that models the internet, road maps, and social networks is a set of names plus a set of pairs. Everything else (adjacency lists, matrices: concept 3) is just repackaging the pairs for faster lookups.

One sanity check you can already run: a connected graph on 6 nodes needs at least 5 edges, and a tree needs exactly n − 1 = 5. Our graph has only 4, so without drawing anything, you know it CANNOT be one connected piece. Counting nodes against edges is often your first clue about a graph's shape.

No root means nobody tells you where to begin

Every tree problem quietly handed you a starting point: the root. Graphs have no root, every node is equally 'the start', and that changes how problems are phrased. Some hand you a start explicitly: Flood Fill says 'begin at pixel (sr, sc)'. Others give no start at all, and that absence is a signal you must TRY EVERY NODE: Number of Islands loops over all cells, launching an exploration from each one not yet visited.

Here is the practical difference: with a root, one traversal covers everything. Without one, a single traversal covers only the piece you started in, from A you would reach 4 of our 6 friends and miss C and F entirely. So read the problem for it: 'start from...' means one traversal; 'count all...' usually means loop over every possible start.

Spotting graphs in the wild

Interview problems almost never say 'here is a graph'. They say 'cities connected by roads' (cities = nodes, roads = edges), 'courses and prerequisites' (courses = nodes, arrows = edges), 'a grid of land and water' (cells = nodes, touching cells = edges), 'words where you may change one letter' (words = nodes, one-letter changes = edges). The moment a problem is about THINGS and CONNECTIONS between them, you are holding a graph.

Train the reflex on every problem ahead: name the nodes, then name the edges, out loud. 'Nodes are cells, edges are the four directions.' 'Nodes are courses, edges are prerequisite arrows.' Once you can say that sentence, the hardest part is done: the remaining concepts supply the machinery.

Directed, Undirected & Weighted

Edges come in flavors. UNDIRECTED edges work both ways (a friendship). DIRECTED edges are one-way arrows (a follow on social media, a course prerequisite). Optionally, edges can carry WEIGHTS, numbers like distance or cost.

# undirected: store BOTH directions
adj[A].push(B);  adj[B].push(A)

# directed: store ONE direction only
adj[A].push(B)            # A -> B

# weighted: store the number too
adj[A].push((B, 268))     # A -> B costs 268

Facebook edges vs Instagram edges

Two apps you know model connection in opposite ways. On Facebook, friendship is MUTUAL: if A is friends with B, then B is friends with A, one fact, usable in both directions. On Instagram, a follow is ONE-WAY: A following B says nothing about whether B follows A back. Same two people, two different edge types: the undirected edge A—B and the directed edge A→B.

Draw a tiny follow graph to carry through this article: A → B (A follows B), and B → C. As an undirected sketch you would shrug, three people, all connected. With arrowheads, position suddenly matters enormously.

Direction rewrites what you can reach

Walk the follow graph A → B → C, always moving WITH the arrows. That is the rule in directed graphs (think of a retweet flowing downstream). From A you reach B in one hop and C in two. From B you reach only C. From C you reach NOBODY: both arrows point in, none point out. Now erase the arrowheads and re-ask: from any of the three you reach the other two. Same nodes, same lines: radically different answers.

That asymmetry is the entire point of directed graphs: 'A can reach B' no longer implies 'B can reach A'. A post by A can reach everyone in this network; a post by C reaches no one. Every directed-graph question (including the Course Schedule problems ahead) lives inside this one-way logic.

In code: two appends or one

The storage difference is a single line. An undirected edge is a fact about BOTH endpoints, so it lands in both adjacency lists. A directed edge belongs to its source only. That one missing append is the entire difference between the two flavors in code. Which is exactly why it is so easy to get wrong.

The bug: directed storage on an undirected problem

Here is the classic failure with real numbers. Problem: n = 2 people, friendships = [[1, 0]], one mutual friendship, so ONE friend circle. You build the adjacency directed out of habit: adj[1] = [0], adj[0] = []. Now count components by scanning nodes 0, 1: node 0 is unvisited → count = 1 → explore from 0 → adj[0] is empty, so the flood claims only {0}. Node 1 is unvisited → count = 2. You report TWO friend circles. The truth is one.

The poison is that it passes on some inputs: had the edge been written [0, 1], the flood from 0 would have found 1 and the answer would look fine. Directed-by-accident bugs survive the sample tests and die on the hidden ones. The vaccine is a habit: the moment you read 'friends', 'connected', 'mutual', or see roads without arrows, type BOTH appends.

Weights, and calling the flavor in five seconds

The third dial an edge can carry is a WEIGHT. A number riding along: kilometres, cost, latency. You store the pair (neighbor, weight) instead of just the neighbor. None of this track's problems need weights (BFS answers our 'shortest' questions because every edge counts as 1), but learn the trigger now: 'shortest' PLUS weighted edges = Dijkstra's algorithm, a tool for later.

In the problems ahead the split is clean: Flood Fill, Number of Islands, Rotting Oranges are undirected and unweighted, grid neighbors simply touch. Course Schedule I and II are directed and unweighted, prerequisite arrows. So end your first read of ANY graph problem with a one-sentence verdict: 'undirected, unweighted' or 'directed, unweighted'. Five seconds, and it steers every decision after.

Storing a Graph: the Adjacency List

Code can't see pictures, we need a data structure. The workhorse is the ADJACENCY LIST: a map from each node to the list of its direct neighbors. There's also the adjacency MATRIX (a 2D grid of 0s and 1s), but the list wins for almost every interview problem.

adj = map of node -> list of neighbors

for (u, v) in edges:
    adj[u].push(v)
    adj[v].push(u)        # undirected: both ways!

adj[A]  ->  [B, D]        # neighbors in O(1)

The input is a pile of pairs

Graph problems rarely hand you a drawing. They hand you numbers: n = 4 nodes labeled 0 to 3, and an edge list like edges = [[0,1], [1,2], [0,3]]. Try answering the most basic question every traversal asks, 'who are 1's neighbors?', straight from that raw list. You must scan ALL of it: [0,1] touches 1, so 0 is a neighbor; [1,2] touches 1, so 2 is a neighbor; [0,3] does not. One question, one full scan.

Now remember that BFS and DFS ask the neighbor question at EVERY node they visit. With E edges that is an O(E) scan per node, on a graph with 10⁵ edges you would re-read the entire input tens of thousands of times. The fix: reorganize the pairs ONCE so the answer becomes instant.

Build the dict by hand, edge by edge

Set up an empty list per node: adj = {0: [], 1: [], 2: [], 3: []}. Feed the edges through, remembering these friendships are mutual (undirected), so each pair writes TWO entries. Edge [0,1]: append 1 to adj[0] and 0 to adj[1] → {0: [1], 1: [0], 2: [], 3: []}. Edge [1,2]: append 2 to adj[1] and 1 to adj[2] → {0: [1], 1: [0, 2], 2: [1], 3: []}. Edge [0,3]: append 3 to adj[0] and 0 to adj[3] → {0: [1, 3], 1: [0, 2], 2: [1], 3: [0]}.

Done: three edges, six appends. Read the finished structure like a phone contact list: 'who are 1's neighbors?' is now adj[1] → [0, 2]. No scan, no search. And notice the bookkeeping invariant: 3 undirected edges produced exactly 2 × 3 = 6 entries. If your total entry count is ever odd, an append went missing somewhere.

The build code, step zero of every solution

Four lines convert any edge list, and they will open nearly every graph solution you write from now on. defaultdict(list) spares you from creating the empty lists by hand; the loop mirrors exactly what you just did on paper. For a DIRECTED graph, delete the second append. That is the entire difference (and the previous concept showed what breaks when you delete it by accident).

Why not a matrix? Run the memory math

The textbook alternative is the adjacency MATRIX: an n × n table where cell [i][j] = 1 if the edge exists. It sounds tidy until you size it. A social-network problem with n = 10⁵ users needs 10⁵ × 10⁵ = 10¹⁰ cells, ten BILLION, even if each user has a handful of friends. At one byte per cell that is roughly 10 GB, for a graph whose actual data (say 2 × 10⁵ friendships) fits in a few megabytes as an adjacency list.

The list stores only what EXISTS: 2E entries total. The matrix also answers the wrong question fast, 'are i and j connected?' is O(1) there, but traversals never ask that. They ask 'give me ALL of i's neighbors', which forces the matrix to scan an entire row of 10⁵ cells to find three friends. Right structure for the right question: the list.

Reading answers straight off the structure

Once adj exists, common questions become one-liners, and traversals become readable. The heart of BFS and DFS is literally 'for nb in adj[node]'. That is why building adj is step zero, before any thinking: the structure does the remembering so the algorithm can do the exploring. In every problem ahead that hands you an edge list (Course Schedule, most prominently), your solution's first three lines will be this build.

Grids Are Graphs in Disguise

Half of all interview 'graph' problems never say the word graph: they hand you a 2D GRID. The secret: every cell is a node, and each cell connects to its 4 neighbors (up, down, left, right). No adjacency list needed; the neighbors are computed from coordinates.

directions = [(-1,0), (1,0), (0,-1), (0,1)]

for (dr, dc) in directions:
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols:
        visit(nr, nc)     # a real neighbor

A graph with no edge list anywhere

Read a typical 'grid' problem: grid = [[1,1,0,0],[1,0,0,1],[0,0,1,1]], return how many groups of connected 1s exist. Connected. Groups. That is component-counting. A graph question, yet there is no node list and no edge list in sight. The mental flip that unlocks all of these: EVERY CELL IS A NODE. Cell (0,0) is a node, cell (2,3) is a node: twelve nodes in this 3 × 4 grid.

And the edges? Two cells are joined exactly when they touch up, down, left, or right. You never receive these edges and never build them. They are implied by geometry, computable from coordinates the moment you need them. A grid is a graph that ships without its wiring diagram, because the wiring is obvious.

Neighbors by hand: center vs corner

Take cell (1,1), row 1, column 1. Apply the four moves to its coordinates: up is (1−1, 1) = (0,1); down is (1+1, 1) = (2,1); left is (1, 1−1) = (1,0); right is (1, 1+1) = (1,2). All four land inside the 3 × 4 board, so (1,1) has four edges. That little arithmetic: add ±1 to one coordinate, IS the edge lookup.

Now the corner (0,0): up gives (−1, 0), but there is no row −1; left gives (0, −1), no column −1. Only down (1,0) and right (0,1) survive. So corners have 2 neighbors, other border cells 3, interior cells 4, and none of that needs special-casing. It falls out automatically once you test every candidate against the board's bounds.

The dr/dc idiom, line by line

Here is the pattern that appears verbatim in every grid problem in this track. Match it to what you just did by hand: the directions list is the four moves; nr, nc is 'apply one move to where I stand'; the if asks 'does this candidate actually exist on the board?'; only survivors get visited. Memorize the block like a times table. You will type it in Flood Fill, Number of Islands, and Rotting Oranges.

The bounds check is the edge-existence test

In an adjacency list, impossible neighbors simply are not in the list: you cannot visit them by accident. Grids are different: you GENERATE all four candidates and must filter the fakes yourself. That is what 0 <= nr < rows and 0 <= nc < cols really means: 'does this edge exist?'. Skip it and nr = rows crashes with IndexError. Worse, Python hides a trap in the other direction: grid[-1][c] does NOT crash. Negative indexing silently wraps to the LAST row, so your flood 'connects' the top edge of the board to the bottom and produces wrong answers with no error message to help you.

Order matters too: bounds first, THEN any value test like grid[nr][nc] == 1. Reading the value of a cell you have not proven to exist is the same crash wearing a different hat.

One flip, the next three problems

Everything you learn on 'real' graphs applies to grids with three substitutions: node → cell (r, c); adj[node] → the directions loop; visited set → a set of (r, c) pairs, or simply marking the cell in place (flipping '1' to '0'). Three of this track's problems are grids: Flood Fill (spreading from a given start cell), Number of Islands (component counting over all cells), Rotting Oranges (BFS waves from many cells at once). When you get there, notice that you are never learning a 'grid technique'. You are running graph traversal through the coordinate lens.

BFS on Graphs

Breadth-First Search explores a graph in expanding waves: your start node, then everything 1 edge away, then 2 edges away, and so on. It's the level-order traversal you learned on trees, with a queue, plus one crucial new ingredient you'll meet in a moment.

bfs(start):
    queue   = [start]
    visited = {start}
    while queue is not empty:
        node = queue.pop_front()
        for nb in adj[node]:
            if nb not in visited:
                visited.add(nb)
                queue.push(nb)

The question BFS answers: 'how few hops?'

Suppose the graph below is a group of friends, and you (node A) want to reach F with the fewest introductions. There are many paths from A to F, some short, some winding. Breadth-First Search finds the SHORTEST one, and it does it with a strategy you already use in real life: check everyone 1 hop away, then everyone 2 hops away, then 3, expanding like a ripple in a pond.

That ripple picture is the entire algorithm. Ring 0 is just A. Ring 1 is A's direct neighbors: B and C. Ring 2 is THEIR unvisited neighbors: D and E. Ring 3 reaches F. Because we never look at ring 3 before finishing ring 2, the FIRST time we touch F we are guaranteed to have arrived by a shortest route, 3 hops, no doubt, no re-checking.

The machinery: a queue and a visited set, traced by hand

Two data structures run the whole show. The QUEUE (first-in, first-out) holds discovered-but-not-yet-processed nodes. It is what keeps the rings in order, because nodes discovered earlier get processed earlier. The VISITED set remembers everyone we've ever discovered, so nobody gets queued twice.

Trace it: start with queue = [A], visited = {A}. Pop A, enqueue its neighbors B and C → queue = [B, C]. Pop B, enqueue D → [C, D]. Pop C, enqueue E → [D, E]. Pop D, enqueue F → [E, F]. Pop E, its neighbor F is ALREADY in visited, skip it → [F]. Pop F: done. Every node entered the queue exactly once, in ring order: A | B C | D E | F.

The code: ten lines, straight from the trace

Here is the exact loop you just executed by hand. Match each line to a move you made: `queue.popleft()` is 'pop the front', the for-loop is 'look at the neighbors', and the visited-check is 'skip anyone already discovered'. Nothing in the code exists that you didn't already do manually.

One detail deserves a spotlight: we add a node to visited WHEN WE ENQUEUE it, not when we later pop it. Keep that in mind for the next section, it's the classic BFS bug.

The classic bug: marking visited too late

Move the `visited.add` from discovery time to pop time and the algorithm still LOOKS right, but watch node F in our trace. D discovers F and enqueues it. Then E ALSO discovers F (F isn't marked yet: it's only sitting in the queue) and enqueues it AGAIN. On big dense graphs this duplication snowballs: the queue bloats with copies, and each copy re-enqueues its own neighbors.

The rule to engrave: a node's fate is sealed the moment it is DISCOVERED. Mark it then. The queue should never contain two copies of anything.

BFS vs DFS: when the ripple beats the dive

DFS (next concept) dives down one path as far as possible before backtracking; BFS expands evenly. Both visit everything in O(V + E), so for 'can I reach X?' or 'count the components', either works. The moment the question contains the words SHORTEST, FEWEST, or MINIMUM MOVES on an unweighted graph, the choice stops being a choice: BFS's ring-order guarantee IS the proof of shortestness, and DFS simply doesn't have it.

You'll see this play out in the problems ahead: Rotting Oranges (fewest minutes) and Word Ladder (fewest word changes) are BFS by necessity, while Number of Islands just needs ANY full exploration, there DFS's shorter code wins.

DFS on Graphs

Depth-First Search dives as deep as possible down one path before backtracking to try alternatives. It's the same recursion you mastered on trees (visit, then recurse on each neighbor) with the visited set standing in for the 'children never repeat' guarantee trees gave you for free.

visited = empty set

dfs(node):
    visited.add(node)
    for nb in adj[node]:
        if nb not in visited:
            dfs(nb)       # dive deeper

Commit to one tunnel at a time

Our friend network again: A knows B and D, B knows E, and E also knows D (edges A–B, A–D, B–E, D–E). You want to visit everyone reachable from A. BFS (last concept) spreads evenly: everyone 1 hop away, then 2. DFS makes the opposite bet: pick ONE neighbor and commit. From A go to B. From B, deeper to E. From E, deeper still to D. Only at a dead end do you walk back and try the tunnels you skipped.

The name says it all: depth first. It visits the same set of nodes BFS does (everything reachable), just in a different order: plunge, then backtrack. And it reuses the exact recursion you wrote for trees, with one graph-flavored addition you can probably guess.

The dive, traced with the call stack

Run it by hand with the call stack in view. The stack is DFS's memory of the route home. Call dfs(A): mark A, loop over adj[A] = [B, D]. First neighbor B is unmarked → call dfs(B) (stack: A, B). Mark B; adj[B] = [A, E]; A is marked, skip; E is unmarked → dfs(E) (stack: A, B, E). Mark E; adj[E] = [B, D]; B marked, skip; D unmarked → dfs(D). Stack: A, B, E, D, four frames deep.

Mark D; adj[D] = [A, E], both marked. Dead end. dfs(D) returns; dfs(E) has no more neighbors, returns; dfs(B) returns; control lands back in dfs(A), which finally checks its second neighbor D... already visited, skip. Done. Visit order: A, B, E, D. Compare BFS from A on the same graph: A, B, D, E. Same four nodes, different itinerary, and that difference is the entire choice between the two algorithms.

Two ways to write the same dive

The recursive version is tree DFS plus a visited check, six lines. The iterative version replaces the call stack with a list you manage yourself: push instead of call, pop instead of return. Both are correct DFS. Prefer the iterative one when the graph can be DEEP: Python caps recursion around 1000 frames, and a snake-shaped path through a 10⁶-cell grid blows straight past that.

Why the visited check is life-or-death here

Tree DFS never needed a visited set because children never point back at ancestors. Graph edges have no such manners: adj[B] contains A. The node we just came from, and A–B–E–D–A is a cycle. Delete the check and trace it: dfs(A) calls dfs(B) calls dfs(E) calls dfs(D) calls dfs(A). Back at A with no memory of having been there, so the loop fires again, and again, until Python kills the run at roughly 1000 frames with RecursionError: maximum recursion depth exceeded.

The placement rule: mark on ARRIVAL. visited.add(node) is the FIRST line inside dfs, before you look at a single neighbor. Marking late (after the neighbor loop, or only in some callers) leaves a window where two paths can both enter the same node.

When DFS is the right tool

DFS and BFS cover identical territory in identical O(V + E) time, so the choice is about ORDER and CODE SIZE. DFS does NOT find shortest paths: in our trace it reached D by the 3-edge route A → B → E → D even though D sits exactly 1 edge from A. If the problem says 'fewest' or 'shortest', DFS is disqualified. But when the job is 'visit everything in a region' (paint a shape, erase an island, collect all connected cells) order is irrelevant and DFS's six-line recursion is the least code that does the job.

That is exactly how the problems ahead split: Flood Fill and Number of Islands use DFS (paint or erase whole regions); Rotting Oranges needs BFS (minutes = waves). You now own both personalities. Next, the safety tool they share gets its own spotlight.

The Visited Set, Your Cycle Insurance

Trees quietly guaranteed that walking 'down' never revisits a node. Graphs make no such promise: cycles and multiple routes mean any traversal WILL loop forever unless you remember where you've been. The visited set is that memory, and it's non-negotiable.

# THE rule for every graph traversal:
if nb not in visited:
    visited.add(nb)       # mark on DISCOVERY
    queue.push(nb)        # (or recurse, for DFS)

# without the visited set,
# any cycle loops forever

Two nodes are enough to break you

You do not need an elaborate cycle to see the disaster, one friendship does it. Take the two-node graph A—B. It is undirected, so adj[A] = [B] and adj[B] = [A]. Traverse with no memory: dfs(A) visits A and walks to its neighbor B. dfs(B) visits B and walks to ITS neighbor... A. dfs(A) again: walks to B. dfs(B): walks to A. The transcript reads dfs(A), dfs(B), dfs(A), dfs(B), ... and nothing in the algorithm can ever stop it.

In practice Python halts you with RecursionError after about 1000 stacked frames; an iterative version just spins forever. Note what caused it: not a rare pathological input, but ANY undirected edge, because storing both directions (correctly!) makes every edge a tiny two-node loop. Unprotected traversal is not 'risky on some graphs'. It is broken on essentially all of them.

The cure: remember where you have been

Add one set and re-run the exact same trace. dfs(A): visited = {A}; A's neighbor B is not in visited → dfs(B): visited = {A, B}; B's neighbor A IS in visited → skip → dfs(B) returns → dfs(A) returns. Two calls, program ends, both nodes seen exactly once. The infinite ping-pong became a two-line transcript because the second visit was refused at the door.

That is the visited set's entire job: turn 'have I been here?' from an unanswerable question into a set-membership check. It also buys the bound you will quote forever: each node processed once, each edge glanced at from each end at most once → O(V + E).

WHEN to mark: arrival vs discovery

The set only protects you if you mark at the right MOMENT, and the moment differs by traversal. DFS marks on ARRIVAL: visited.add(node) is the first line of the function, before any neighbor is examined. BFS marks on DISCOVERY: the instant a neighbor is appended to the queue, NOT later when it is popped. The late-marking BFS bug is sneaky because the code still terminates and still looks right: but a node discovered by two different parents enters the queue twice, doing duplicate work, B and D both enqueueing E in the last concept's graph, and corrupting distance counts in shortest-path problems.

Directed graphs: a revisit is not a cycle

One nuance to file away for the Course Schedule problems. On a DIRECTED graph, 'I have seen this node before' does not prove a cycle. Picture the diamond Intro → DSA, Intro → ML, DSA → AI, ML → AI: exploring from Intro REACHES AI twice, once down each branch, yet no arrow ever points backward, so there is no cycle. The plain visited set does the right thing for traversal (AI gets explored once), but if you shouted 'cycle!' at every revisit, you would cry wolf on this perfectly legal graph.

True directed-cycle detection asks a sharper question: is this node on my CURRENT path? The classic tool is three colors (white (never seen), gray (on the current dive), black (fully finished)) and only stepping on GRAY means a real cycle. Keep it gentle for now: in this track you will detect directed cycles with Kahn's algorithm instead (two concepts ahead), which reaches the same verdict using nothing but counters.

The habit that makes it automatic

Every graph traversal you write from here on has three parts: a worklist (queue, stack, or the call stack), the neighbor loop, and the visited set. The first two get all the attention; the third decides whether your program ends. Build the reflex now: every single problem ahead, from Flood Fill to Course Schedule, will exercise it, and let your hands type 'visited = set()' before your brain finishes reading the problem statement.

Connected Components

A connected component is a group of nodes that can all reach each other. A graph may fall apart into several such pieces, and 'how many pieces?' is one of the most common graph questions, usually wearing a costume like 'count the islands' or 'count the friend circles'.

count = 0
visited = empty set

for node in all_nodes:
    if node not in visited:
        count += 1        # a new piece!
        flood(node)       # BFS/DFS claims the piece

return count

How many separate friend circles?

Back to the friend network: A–B, A–D, B–E, and separately C–F. Start a rumor at A and it reaches B, D, E, never C or F. Start one at C and it reaches only F. This graph is not one community; it is TWO islands of friendship, and no amount of walking crosses the water between them. Each island is a CONNECTED COMPONENT: a maximal group of nodes that can all reach each other.

'How many components?' is one of the most-asked graph questions, always in costume: 'count the islands', 'how many friend circles?', 'how many provinces?'. One traversal cannot answer it: a flood from A paints exactly A's island and stops at the shoreline. You need a loop AROUND the flood.

Roll call + flood, traced end to end

The pattern has two layers. OUTER: a roll call over every node in order, A, B, C, D, E, F. INNER: whenever roll call lands on a node with no breadcrumb, you have discovered a brand-new island → count it, then flood it (DFS or BFS, either works) to mark every member. Trace: A is unvisited → count = 1, flood claims {A, B, D, E}. Roll call reaches B, visited, skip. C: unvisited! count = 2, flood claims {C, F}. D, E, F, visited: skip, skip, skip. Final count: 2.

Read the numbers again: 6 nodes, but only 2 flood LAUNCHES, and the count tracks launches, not nodes. Each launch claims its entire island before roll call resumes, so when roll call later reaches that island's other members, they are already marked. Only the FIRST-found node of each island fires the counter. That division of labor is the whole trick.

The code: eight lines around a flood

Here is the whole thing. The dfs is the same six-line flood from two concepts ago; the new part is only the wrapper. The for-loop is the roll call, the if is the breadcrumb check, and count += 1 fires exactly once per launch. Swap the dfs for a BFS and nothing else changes. The counting never cares HOW an island gets painted, only that one launch paints all of it.

The classic miscount: nodes instead of launches

The signature bug is incrementing per NODE instead of per LAUNCH, and it happens two ways. Way one, you forget the flood entirely: roll call finds A unvisited (count 1), then B unvisited (count 2), then C (3)... final answer 6, one per node. Way two, subtler: your flood forgets to MARK what it visits: the flood from A happily walks through B, D, E but leaves no breadcrumbs, so roll call later 'discovers' B, D, E again as fresh islands. Same inflated answer, and it looks like the counting is broken when really the marking is.

The invariant to check whenever your count comes out too high: after the flood from X returns, EVERY node reachable from X must be in visited. And it must be ONE visited set shared across all launches. A fresh set per launch recounts everything.

Where this pattern shows up next

Number of Islands is literally this code on a grid: the roll call becomes a double loop over every cell, 'unvisited' becomes 'holds a 1 and is not marked', and the flood runs through the four directions. Number of Provinces is the same wrapper over a different input format. The complexity survives the nesting, too: the roll call touches n nodes, and all the floods COMBINED touch each node and edge once (the shared visited set guarantees it), O(V + E) total, not O(V × E).

One edge case worth engraving: a node with no edges at all is still a component. Roll call finds it unvisited, launches a flood that marks just it and returns, count += 1. Isolated nodes count: remember that when a problem says n = 5 but the edge list only mentions four people.

Topological Sort: Ordering with Arrows

On a DIRECTED graph where arrows mean 'must come before', a topological order is any line-up of the nodes that respects every arrow. It exists exactly when the graph has NO cycles, and the algorithm that finds it (Kahn's algorithm) also detects when a cycle makes ordering impossible.

indegree[n] = number of arrows INTO n
queue = [nodes with indegree 0]
order = []

while queue is not empty:
    n = queue.pop_front();  order.push(n)
    for nb in adj[n]:
        indegree[nb] -= 1
        if indegree[nb] == 0: queue.push(nb)

if length(order) < total nodes  ->  cycle!

Four courses, four arrows, one question

Four courses with prerequisite arrows: Intro → DSA, Intro → ML, DSA → AI, ML → AI (an arrow means 'take this first'). You must pick an order that takes all four while violating no arrow. Eyeball it and two orders work: Intro, DSA, ML, AI, or Intro, ML, DSA, AI. Both are valid TOPOLOGICAL ORDERS: line-ups where every arrow points forward, never backward.

Eyeballing dies at 40 courses. You need a mechanical rule, and the right one is exactly how you would actually plan a degree: each semester, take whatever has all of its prerequisites already done. That everyday instinct, formalized, is Kahn's algorithm.

Indegree = prerequisites not yet done

For each course, count the arrows pointing INTO it, its INDEGREE. Intro: 0 arrows in. DSA: 1 (from Intro). ML: 1 (from Intro). AI: 2 (from DSA and from ML). Read indegree as 'unmet prerequisites'. A course with indegree 0 is takeable RIGHT NOW, and Intro. The only 0: is therefore the only legal first course. The whole algorithm will be: take a 0, update the counts, repeat until nothing is left.

Kahn's peeling, semester by semester

Seed the ready queue with every indegree-0 course: [Intro]. Now peel. Take Intro (order: [Intro]); finishing it satisfies one prerequisite of each course it points to, so decrement their indegrees: DSA 1 → 0 (ready, enqueue), ML 1 → 0 (ready, enqueue). Take DSA (order: [Intro, DSA]); AI drops 2 → 1. Still blocked, so it does NOT enter the queue. Take ML (order: [Intro, DSA, ML]); AI drops 1 → 0, enqueue. Take AI. Final order: [Intro, DSA, ML, AI], 4 of 4 processed, every arrow respected.

Notice AI waited until BOTH parents were peeled, the counter enforced that automatically. And notice the tie after Intro: DSA and ML were both ready, and either could have gone first. Topological orders are not unique; any line-up violating no arrow is a correct answer.

The code: a BFS with a gate

Kahn's is structurally BFS with one twist: a node does not enter the queue when it is DISCOVERED, it enters when its indegree hits 0, i.e., when its LAST prerequisite completes. The final length check is the payoff line: if the loop processed fewer nodes than exist, the leftovers are stuck in a cycle.

Cycle = deadlock, and the count exposes it

Add one bad arrow: AI → Intro. Recount the indegrees: Intro 1, DSA 1, ML 1, AI 2. No zeros ANYWHERE: the ready queue starts empty, the while loop never runs, and order finishes empty: 0 of 4 processed. That is not a crash; it is a diagnosis. Every course in the loop Intro → DSA → AI → Intro waits on another, exactly like 'you need experience to get a job and a job to get experience'. Deadlock.

In mixed graphs the cycle traps only its own members plus everything downstream of them: the honest part of the graph still gets ordered, the trapped part never reaches indegree 0, and len(order) < n reports it. One comparison, two products: the order when it exists, the cycle verdict when it does not.

Where you will meet it

Course Schedule I ('can you finish all courses?') is Kahn's with the answer len(order) == n. Course Schedule II ('give me a valid order') is Kahn's returning the order itself. You will build both a few lessons from now. Outside interviews it runs anywhere order-with-dependencies lives: build systems compiling files before the files that import them, spreadsheets recalculating cells before their dependents, package managers installing a library before the apps that need it.

The Graph Problem Checklist

Every graph problem yields to the same four questions: (1) Is this secretly a graph? (2) How is it represented, and do I need to convert? (3) BFS or DFS? (4) How do I track visited? Answer those and the code mostly writes itself.

# before ANY graph problem:
1. RECOGNIZE   connections? spreading? ordering?
2. REPRESENT   adjacency list / grid + directions
3. TRAVERSE    BFS (waves) · DFS (dive) · topo sort
4. TRACK       visited = set(), always

Five questions replace the panic

You open an unseen graph problem and the clock is running. The wrong move is rummaging through memory for 'the trick'. The right move is interrogation. Five short questions whose answers assemble the solution for you: (1) Directed or undirected? (2) Weighted? (3) Grid or edge list? (4) Shortest path, or just reachability? (5) One source, or components everywhere? You already met every answer in the previous nine concepts; this page bolts them into a fixed order.

Each question changes exactly one thing about your solution. The build, the tool, the plumbing, the traversal, the wrapper. Run all five on every problem in this track; by the third problem the interrogation takes fifteen seconds.

Q1 directed? · Q2 weighted?

Q1 changes your BUILD and your toolbox. Undirected ('friends', 'connected', 'roads'): two appends per edge, and flooding/components are on the table. Directed ('follows', 'prerequisite', 'depends on'): one append, reachability becomes one-way, and topological sort enters the toolbox. Get Q1 wrong and nothing downstream can save you: remember concept 2's bug, where one-way storage of a mutual friendship counted 2 components instead of 1.

Q2 changes the SHORTEST-PATH tool. Unweighted, every edge counts as 1, means BFS's ring order IS shortest, done. Weighted (edges carry km, cost, milliseconds) kills that guarantee: a 2-edge route can cost more than a 5-edge one, and you would need Dijkstra, which is beyond this track. Everything here is unweighted; spotting weights in the wild is your cue that plain BFS will not cut it.

Q3: grid or edge list?

This one decides your first five lines. Edge list input → build the adjacency dict before any thinking: defaultdict(list), loop, one or two appends per Q1's answer. Grid input → build NOTHING: the directions array plus a bounds check is your adjacency, computed on the fly, and marking cells in place can replace the visited set. The algorithms on top are identical; only the neighbor-lookup plumbing changes.

Q4 shortest or reach? · Q5 one source or components?

Q4 picks the traversal. The words 'shortest', 'fewest', 'minimum steps/minutes' on an unweighted graph → BFS, no debate: only its ring-by-ring order proves minimality. If the ask is merely 'reach it / paint it / erase it / count it', order does not matter → DFS or BFS are both correct, and DFS usually wins on code length.

Q5 picks the wrapper AROUND the traversal. Start given ('begin at pixel (sr, sc)') → one flood, no wrapper. No start given plus 'count the pieces' → the roll-call loop: visit every node, flood at each unvisited one, count launches. Everything starts at once ('every rotten orange spreads each minute') → multi-source BFS: seed the queue with ALL the sources at distance 0, then run plain BFS. Three wrappers, and you have now seen each one in this track.

The decision table

The nine concepts compressed into lookup form: match the problem's ask on the left, take the tool on the right. This table is what your brain should retrieve when you open the problems ahead, and after this track, it is what interview graph questions decompose into.

Check yourself: three problems, no code

Run the interrogation on these three. Answers follow immediately, so cover them for an honest test. (1) 'A maze of open and blocked cells: fewest steps from entrance to exit?' (2) 'n = 5 people, friendships [[0,1], [2,3]]. How many friend groups?' (3) 'Course pairs [a, b] mean you must take b before a, can you finish all courses?'

Answers. (1) Undirected, unweighted, GRID, shortest, single source → BFS over cells with the directions array, visited marked at enqueue; the answer is the ring number where the exit first appears. (2) Undirected: two appends!, edge list, no start given, counting pieces → roll call + flood: {0,1} is one group, {2,3} another, and person 4, touched by no edge, is a component alone. Answer: 3, forgetting the isolated node is THE classic slip. (3) DIRECTED ([a, b] is the edge b → a: watch the order), edge list, ordering question → Kahn's algorithm; the answer is yes exactly when processed == n.

All DSA learning paths