Graphs

Graphs generalize trees: instead of a single parent per node, any node can connect to any other, in any pattern — cycles included. That extra freedom is exactly why this is the topic interviews lean on most: almost any "how are these things related/reachable/orderable" question, however it's dressed up (a grid, a word list, a course catalog, a network), is a graph problem wearing a costume.

The two traversals you already know, generalized

BFS and DFS aren't new here — Trees already used both. The difference is that a graph node can be reached more than one way, so every traversal needs an explicit visited set (a tree never revisits a node by construction; a graph absolutely can, including right back to where you started). Number of Islands and Flood Fill are the clearest versions of this: BFS outward from a cell, marking each one visited the moment you enqueue it, so a cycle in the grid's connectivity never re-processes the same cell twice.

Topological sort: ordering with constraints

Course Schedule asks "is there a valid order at all" (does the dependency graph have a cycle); Course Schedule II asks for the order itself. Both use the same algorithm — Kahn's algorithm: track each node's in-degree (how many prerequisites point at it), seed a queue with every in-degree-0 node, and repeatedly pop one, "complete" it, and decrement its neighbors' in-degrees, pushing any that just hit 0. If every node eventually gets popped, there's no cycle; anything left over is stuck in one. The queue is what keeps this O(V + E) — rescanning every node each round for one with in-degree 0, instead of remembering which ones just became available, turns this into O(V²) for no reason.

Union-Find: is this the same component as that?

Number of Connected Components, Graph Valid Tree, and Redundant Connection all ask a version of "are these two nodes already connected" — repeatedly, as edges are added one at a time. A Disjoint Set Union structure answers that in near-O(1) per query, but only with two specific optimizations working together: path compression (every find flattens the path it just walked, so future lookups on those nodes are instant) and union by rank (always attach the shorter tree under the taller one, keeping trees shallow to begin with). Drop either one, and a specific adversarial sequence of unions can build a tree of depth n — turning "near O(1)" into genuinely O(n) per lookup.

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]); // path compression
    return parent[x];
}
bool unite(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return false; // already connected
    if (rank_[ra] < rank_[rb]) std::swap(ra, rb); // union by rank:
    parent[rb] = ra;                          // attach the SHORTER tree under the taller one
    if (rank_[ra] == rank_[rb]) rank_[ra]++;
    return true;
}

BFS finds shortest paths — for free, in unweighted graphs

Word Ladder and Rotting Oranges look unrelated (a dictionary vs. a grid) but are the same idea: BFS naturally explores in order of distance from the start, so the first time it reaches any node is necessarily via a shortest path. Word Ladder's efficiency trick is in how it generates neighbors — trying all 26 possible letters at each position (a fixed 26·L candidates) instead of comparing every pair of words in the dictionary (which is O(N²) for no reason). Rotting Oranges' trick is starting the BFS from every rotten orange at once — a "multi-source" BFS — so all of them spread in parallel in one pass, rather than running a separate BFS per source and combining the results afterward.

When edges have weights: Dijkstra

Network Delay Time is the one problem here where "fewest edges" isn't the same as "least total cost" — a 2-hop path can beat a 1-hop path if the 1-hop edge is expensive enough. Dijkstra's algorithm is BFS's natural generalization for this: instead of a plain queue, a min-heap keyed by current best-known distance always expands the closest unfinished node next. The heap is what keeps this O(E log V); without it, finding "the closest unfinished node" each round means scanning all V of them, which is O(V²) — the same recompute-vs-maintain distinction that shows up throughout this course.

Common mistakes

• Forgetting the visited set — the single most common graph bug; without it, a cycle in the input turns a traversal into an infinite loop instead of just revisiting a node harmlessly.
• Recursive DFS on a graph that might be huge and densely connected — correct in theory, but a real stack-overflow risk in practice; BFS with an explicit queue sidesteps this entirely.
• Union-Find with only one of the two optimizations — "it has path compression, that's enough" (or vice versa for rank) is a common half-truth; either one alone still allows a bad case, just a different one.
• Treating a weighted shortest-path problem like an unweighted one — plain BFS assumes every edge costs the same "1 step"; the moment edges have different weights, only Dijkstra (or another weighted-shortest-path algorithm) gives a correct answer.