Representation — adjacency list and grids

Recognize it from

A list of edges, a matrix of 0/1 cells, words like reachable / connected / spread / shortest on a grid. Four questions: directed?, weighted?, cyclic?, connected?

What it actually does

A graph is nodes plus edges. An adjacency list stores, for each node, the nodes you can walk to in one step. Interview graphs are almost always sparse, so a list is the default: space O(V+E) instead of O(V²) for a matrix of “no edge” cells.

A grid is the same object with a different costume. Each cell is a node. The four (sometimes eight) in-bound neighbors are edges. You rarely build adj explicitly — you compute neighbors from dirs when you need them.

// n = 3 nodes, undirected edges 0-1 and 1-2
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); // one bucket per node id
adj.get(0).add(1);
adj.get(1).add(0); // undirected: write both directions
adj.get(1).add(2);
adj.get(2).add(1);

List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
    adj.get(e[0]).add(e[1]);
    adj.get(e[1]).add(e[0]); // delete this line for a directed graph
}
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}}; // grid: right, left, down, up
// cell (r,c) is a node; neighbor (r+dr, c+dc) is an edge if in bounds

Example 1 — simple

Three nodes, two undirected edges. Node ids are 0, 1, 2.

From 0 you can only reach 1 in one step. From 1 you can reach 0 or 2. There is no 0–2 edge.

Example 2 — every step

A 2×3 grid. Cell (r,c) is a node. Walk every neighbor of the center-left cell (1,1) with dirs.

E’s neighbors are B, D, F. Same BFS/DFS as on adj, with bounds checks instead of a list lookup.

Breadth-First Search (BFS)

Recognize it from

“Shortest path,” “minimum steps / moves / operations,” “fewest minutes until …,” in an unweighted graph or grid. Rotting oranges, word ladder, open-the-lock, knight hops, reduce-n-by-a-digit.

What it actually does

BFS explores every node at distance 1 before any node at distance 2. A queue (FIFO) is what makes that true: you finish the older, closer nodes before the newer, farther ones. The first time you reach a node is therefore via a shortest path. Weighted edges break this — then you need Dijkstra or Bellman-Ford.

Mark a node visited when you enqueue it, not when you poll it. If you wait until poll, two parents at the same distance can both push the same child, and the queue fills with duplicates. On a grid that mistake turns an O(mn) walk into a much larger bag of repeated cells.

void bfs(List<List<Integer>> adj, int start, boolean[] visited) {
    Queue<Integer> q = new ArrayDeque<>();
    visited[start] = true; // mark on ENQUEUE — before anyone else can push start again
    q.offer(start);
    while (!q.isEmpty()) {
        int u = q.poll(); // FIFO: oldest (closest) node comes out first
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                visited[v] = true; // mark NOW, not when we poll v later
                q.offer(v);
            }
        }
    }
}

int[] bfsDist(List<List<Integer>> adj, int start, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, -1); // -1 = not reached (also the visited flag)
    Queue<Integer> q = new ArrayDeque<>();
    dist[start] = 0;
    q.offer(start);
    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : adj.get(u)) {
            if (dist[v] == -1) { // first time we see v — this path is shortest
                dist[v] = dist[u] + 1;
                q.offer(v);
            }
        }
    }
    return dist; // -1 remains for unreachable nodes
}
// Multi-source: offer EVERY source first (all rotten oranges, all gates), dist=0,
// then the same loop. One layer of the queue = one minute / one step.

Example 1 — simple

Line graph, start at 0. You should be able to finish this table without looking at the code.

Visit order 0, 1, 2. Distances from 0: [0, 1, 2]. There is no shorter way to 2 than two edges.

Example 2 — every step

Same drawing the rest of this chapter reuses. Start at 0. Notice 3 and 4 are both distance 2 — BFS must finish 1 and 2 before touching them.

Final distances from 0: [0, 1, 1, 2, 2]. Visit order 0, 1, 2, 3, 4. The edge 3–4 is examined but never improves a distance — both ends were already reached on a shorter path. Swap the queue for a stack and you get DFS, which on this graph visits 0, 1, 3, 4, 2 and loses the shortest-path guarantee if edges had different lengths (even here the visit order is no longer by distance).

Depth-First Search (DFS)

Recognize it from

Connected components, “does a path exist,” number of islands, clone a graph, exhaustive exploration, and the skeleton of backtracking. Interviewers sometimes ask for the iterative version to check you know what recursion is doing.

What it actually does

DFS fully explores one neighbor’s branch before trying the next neighbor. Recursion makes that automatic: dfs(v) does not return until everything reachable from v through unused nodes is finished. The Java call stack holds one frame per node on the current path — that frame remembers which node and where in the neighbor loop you are. That is why a chain of V nodes uses O(V) stack space, not “some small height H.”

Mark visited on entry (the first time you arrive). If you mark on exit, a cycle can recurse forever because the neighbor still looks unused. Iterative DFS uses an explicit Deque as a stack. Order can differ from recursive DFS unless you push neighbors in reverse so the first neighbor is the first one popped.

BFS vs DFS on the same graph is the picture to remember: BFS walks by distance; DFS walks by “go left until you cannot.” Neither is “better.” Shortest unweighted path is BFS. Components, cycle-in-directed (3-state), and backtracking are DFS.

void dfs(int u, List<List<Integer>> adj, boolean[] visited, List<Integer> order) {
    visited[u] = true; // arriving for the FIRST time — mark before neighbors
    order.add(u); // preorder: record on entry (postorder would add after the loop)
    for (int v : adj.get(u)) {
        if (!visited[v]) {
            dfs(v, adj, visited, order); // go DEEP. this call returns only when v's branch is done
        }
        // if visited[v] is true, v is on this path or an earlier finished path — skip
    }
    // no more unused neighbors. this stack frame pops. the caller continues ITS for-loop
}
// start: Arrays.fill(visited,false); dfs(start, adj, visited, order);

// Recursive — the JVM call stack IS the stack. Loop all nodes for a disconnected forest.
void dfsAll(List<List<Integer>> adj, int n, List<Integer> order) {
    boolean[] visited = new boolean[n];
    for (int i = 0; i < n; i++) {
        if (!visited[i]) dfs(i, adj, visited, order); // new component
    }
}
void dfs(int u, List<List<Integer>> adj, boolean[] vis, List<Integer> order) {
    vis[u] = true;
    order.add(u);
    for (int v : adj.get(u)) {
        if (!vis[v]) dfs(v, adj, vis, order);
    }
}

// Iterative — same idea, Deque used as a stack. A node can be pushed twice;
// skip if already visited when it is popped (unlike BFS, we often mark on POP here
// because we push neighbors in reverse to mimic recursive left-to-right).
List<Integer> dfsIterative(List<List<Integer>> adj, int start, int n) {
    List<Integer> order = new ArrayList<>();
    boolean[] vis = new boolean[n];
    Deque<Integer> st = new ArrayDeque<>();
    st.push(start);
    while (!st.isEmpty()) {
        int u = st.pop();
        if (vis[u]) continue; // duplicate push from two parents
        vis[u] = true;
        order.add(u);
        List<Integer> nbrs = adj.get(u);
        for (int i = nbrs.size() - 1; i >= 0; i--) { // reverse so first neighbor is popped first
            int v = nbrs.get(i);
            if (!vis[v]) st.push(v);
        }
    }
    return order;
}

Example 1 — simple

Same 3-node line as BFS Example 1, so you can compare. Recursive DFS from 0. Neighbor lists: 0→[1], 1→[0,2], 2→[1].

DFS order 0, 1, 2 — on a line it matches BFS. The difference shows up as soon as a node has two unused neighbors (Example 2).

Example 2 — every step

The diamond. Recursive DFS from 0, neighbors in increasing id: 0→[1,2], 1→[0,3], 2→[0,4], 3→[1,4], 4→[2,3]. Watch the stack go down 0-1-3-4-2, then unwind, and see that when dfs(0) would try neighbor 2, 2 is already visited via 4.

DFS visit order: 0, 1, 3, 4, 2. BFS on the same drawing was 0, 1, 2, 3, 4. Both visit every node; only BFS groups them by distance from 0.

Iterative stack after pushing 0, if we push neighbors in reverse so 1 is popped first: pop 0, push 2 then 1 (reverse of [1,2]), pop 1, … — you can match the recursive order. If you push left-to-right you get a different but still valid DFS.

Cycle detection — directed vs undirected

Recognize it from

“Detect a cycle,” “can you finish all courses,” anything that must prove a graph is a DAG before topological sort. Directed and undirected are different algorithms. A boolean visited array is not enough on a directed graph.

What it actually does

Undirected: every edge is two-way, so the edge you just walked, back to your parent, is not a cycle. A cycle is “I reached an already-visited node that is not my parent.”

Directed: there is no “parent edge is harmless” rule. You must know whether a node is on the active recursion path (gray) versus fully finished (black). An edge into a gray node is a back-edge = cycle. An edge into a black node is a cross/forward edge into an already-safe region — not a cycle.

// UNDIRECTED — the edge back to parent is not a cycle
boolean cycleU(int u, int parent, List<List<Integer>> adj, boolean[] vis) {
    vis[u] = true;
    for (int v : adj.get(u)) {
        if (!vis[v]) {
            if (cycleU(v, u, adj, vis)) return true;
        } else if (v != parent) {
            return true; // visited and not where we came from → a back edge
        }
    }
    return false;
}

// DIRECTED — 0 unseen, 1 on the CURRENT path (gray), 2 finished (black)
boolean cycleD(int u, List<List<Integer>> adj, int[] state) {
    state[u] = 1; // entering: this node is in-progress
    for (int v : adj.get(u)) {
        if (state[v] == 1) return true; // edge into a gray node = directed cycle
        if (state[v] == 0 && cycleD(v, adj, state)) return true;
        // state[v]==2: that branch is done and acyclic — ignore
    }
    state[u] = 2; // leaving: safe forever, other DFS trees may still start
    return false;
}
boolean hasCycleDirected(List<List<Integer>> adj, int n) {
    int[] state = new int[n];
    for (int i = 0; i < n; i++) {
        if (state[i] == 0 && cycleD(i, adj, state)) return true;
    }
    return false;
}

Example 1 — simple

Directed 2-cycle: 0→1 and 1→0. 3-state DFS from 0.

If you had used a single boolean, after finishing some other component you could still mis-read a finished node as a cycle. The gray state is the whole trick.

Example 2 — every step

Directed: 0→1, 1→2, 2→0, 2→3. The cycle is 0-1-2-0. 3 is a dangling sink.

On an undirected copy of 0-1-2-0, the parent skip is required: from 1, neighbor 0 is visited but 0 is parent — not a cycle yet. From 2, neighbor 0 is visited and is not parent → cycle.

Topological sort — Kahn and DFS postorder

Recognize it from

Prerequisites, build order, course schedule, task dependencies, alien dictionary, delivery stations + classes. Only valid on a DAG. If a cycle exists there is no order.

What it actually does

Kahn’s algorithm is BFS on indegrees. A node whose indegree is 0 has no unmet prerequisites — emit it, then “unlock” its neighbors by subtracting one from their indegree. If you cannot emit n nodes, the leftovers are on a cycle.

DFS topo is the same constraint in reverse: you may output a node only after every node it points to is already output. That is postorder, then reverse (or push onto a stack and pop).

// Kahn: start with indegree 0, peel those nodes, reduce neighbors
List<Integer> kahn(List<List<Integer>> adj, int n) {
    int[] indeg = new int[n];
    for (List<Integer> nbrs : adj) for (int v : nbrs) indeg[v]++;
    Queue<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
    List<Integer> order = new ArrayList<>();
    while (!q.isEmpty()) {
        int u = q.poll();
        order.add(u);
        for (int v : adj.get(u)) {
            if (--indeg[v] == 0) q.offer(v); // last remaining prereq just got done
        }
    }
    return order.size() == n ? order : List.of(); // leftover nodes = cycle
}

// DFS topo: push a node AFTER every descendant is done (postorder), then reverse
void dfsTopo(int u, List<List<Integer>> adj, int[] state, Deque<Integer> st) {
    state[u] = 1;
    for (int v : adj.get(u)) {
        if (state[v] == 1) throw new IllegalStateException("cycle");
        if (state[v] == 0) dfsTopo(v, adj, state, st);
    }
    state[u] = 2;
    st.push(u); // postorder: dependents already in the stack under us
}
// pop the deque for the order. size < n or a throw means a cycle.

Example 1 — simple

Two courses: edge 0→1 means “0 before 1” (0 is a prereq of 1). Indegree [0, 1].

Order [0, 1]. If you also had 1→0, indegrees start at [1,1], queue is empty, order size 0 < 2 → cycle.

Example 2 — every step

Courses 0,1,2,3. Edges 0→1, 0→2, 1→3, 2→3 (“0 before 1 and 2; 1 and 2 before 3”).

Valid order 0, 1, 2, 3 (or 0, 2, 1, 3 if 2 was dequeued first). order.size()==4 so no cycle. Delivery-stations on LC 6369243 is this shape on that IE — do not stamp LC 210 on that post.

Union-Find (Disjoint Set)

Recognize it from

Connected components without a full DFS, “are these two in the same group,” redundant connection, number of provinces, Kruskal’s MST cycle check. Not the default for directed graphs.

What it actually does

Each node starts as its own set. find(x) returns the representative (root) of x’s set. union(a,b) merges the two sets if they differ. If they already share a root, the edge a–b is redundant — it would create a cycle in an undirected graph.

Path compression flattens the tree while you find. Union by rank hangs the smaller tree under the larger. Together, each operation is amortized almost O(1).

int[] parent;
int find(int x) {
    while (parent[x] != x) x = parent[x]; // walk up to the root — no compression yet
    return x;
}
void union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return; // already one set — this edge would close a cycle
    parent[rb] = ra; // hang b's tree under a's root
}

int[] parent, rank;
int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]); // path compression
    return parent[x];
}
void union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return;
    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
    parent[rb] = ra;
    if (rank[ra] == rank[rb]) rank[ra]++;
}

Example 1 — simple

Three nodes. union(0,1) then find(1) vs find(2).

0 and 1 are connected. 2 is not. A later union(1,2) would merge 2 under 0.

Example 2 — every step

Six elements. union(0,1), union(1,2), union(3,4), union(2,3). Rank + compression as in the interview code.

Sets: {0,1,2,3,4} and {5}. Calling find(4) now walks 4→3→0 and compresses parent[4]=0 (and parent[3]=0 on the way back).

Dijkstra — weighted shortest path, non-negative weights

Recognize it from

Shortest path when edges have weights ≥ 0. Network delay time, cheapest flights without a hop cap (hop cap is often Bellman-Ford / limited BFS).

What it actually does

Always settle the unsettled node whose current distance is smallest. Because remaining edges only add (never subtract), that distance can never improve later. A min-heap of (node, dist) candidates implements “who is closest.” Java’s PriorityQueue does not support decrease-key, so you push a new pair and skip stale pops with d > dist[u].

A negative edge breaks the “settled forever” claim. Then Bellman-Ford.

// Tiny version: scan for the unfinalized node with smallest dist each round (O(V²))
int[] dijkstraSlow(int[][] w, int src, int n) { // w[u][v] = weight or INF
    int[] dist = new int[n];
    boolean[] done = new boolean[n];
    Arrays.fill(dist, Integer.MAX_VALUE / 4);
    dist[src] = 0;
    for (int k = 0; k < n; k++) {
        int u = -1;
        for (int i = 0; i < n; i++) if (!done[i] && (u < 0 || dist[i] < dist[u])) u = i;
        done[u] = true;
        for (int v = 0; v < n; v++) dist[v] = Math.min(dist[v], dist[u] + w[u][v]);
    }
    return dist;
}

int[] dijkstra(List<List<int[]>> adj, int src, int n) { // int[]{to, weight}
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE / 4);
    dist[src] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
    pq.offer(new int[]{src, 0});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int u = cur[0], d = cur[1];
        if (d > dist[u]) continue; // stale heap entry — ignore
        for (int[] e : adj.get(u)) {
            int v = e[0], w = e[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{v, dist[v]}); // leave the old worse pair in the heap
            }
        }
    }
    return dist;
}

Example 1 — simple

Three nodes. 0→1 weight 5, 0→2 weight 1, 2→1 weight 1. Source 0.

Answer [0, 2, 1]. The path 0→2→1 beat the direct edge.

Example 2 — every step

0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5). Source 0.

Final [0, 3, 1, 4]. Cheapest Flights Within K Stops is not plain Dijkstra — the hop limit needs a modified Bellman-Ford or BFS with (node, hops).

Bellman-Ford — negatives and negative-cycle check

Recognize it from

Negative weights allowed, or “detect a negative cycle,” or cheapest flights with at most K stops (relax K+1 rounds).

What it actually does

Relax every edge, V−1 times. A shortest simple path uses at most V−1 edges, so that many rounds are enough if there is no negative cycle. A V-th improving relaxation means a path with ≥ V edges got shorter — that path repeated a vertex, and the cycle’s total weight is negative.

// One extra round after V-1 is the negative-cycle check
int[] bf(int[][] edges, int n, int src) { // edges: u, v, w
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE / 4);
    dist[src] = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
        }
    }
    return dist;
}

int[] bellmanFord(int[][] edges, int n, int src) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE / 4);
    dist[src] = 0;
    for (int i = 0; i < n - 1; i++) {
        boolean any = false;
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; any = true; }
        }
        if (!any) break; // already stable
    }
    for (int[] e : edges) {
        int u = e[0], v = e[1], w = e[2];
        if (dist[u] + w < dist[v]) throw new IllegalStateException("neg cycle");
    }
    return dist;
}

Example 1 — simple

0→1 weight 4, 1→2 weight −2. Source 0. After round 1: dist [0,4,2]. Further rounds change nothing. No cycle.

Example 2 — every step

S=0→A=1 w4, S→B=2 w5, A→B w−2, B→C=3 w3, A→C w10.

K-stop cheapest flights: you only run K+1 relaxation rounds (paths with at most K+1 edges), not necessarily V−1.

Minimum spanning tree — Kruskal and Prim

Recognize it from

Connect all nodes with minimum total cost, min cost to connect all points. Kruskal is sort-edges + Union-Find. Prim is grow-a-tree + heap.

What it actually does

A spanning tree on V nodes has exactly V−1 edges and no cycle. Kruskal considers edges cheapest-first and skips any edge whose ends are already in the same set. Prim, from a start node, repeatedly adds the cheapest edge that reaches a new node.

// Kruskal needs Union-Find from the previous card
int kruskal(int[][] edges, int n) { // each edge [u,v,w]
    Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
    parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    int cost = 0, used = 0;
    for (int[] e : edges) {
        if (find(e[0]) == find(e[1])) continue; // would cycle
        union(e[0], e[1]);
        cost += e[2];
        if (++used == n - 1) break;
    }
    return cost;
}

// Prim sketch: grow one tree, heap of edges that leave the tree
int prim(List<List<int[]>> adj, int n) {
    boolean[] in = new boolean[n];
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
    pq.offer(new int[]{0, 0}); // node, cost to attach
    int cost = 0, taken = 0;
    while (!pq.isEmpty() && taken < n) {
        int[] cur = pq.poll();
        int u = cur[0], w = cur[1];
        if (in[u]) continue;
        in[u] = true;
        cost += w;
        taken++;
        for (int[] e : adj.get(u)) if (!in[e[0]]) pq.offer(new int[]{e[0], e[1]});
    }
    return taken == n ? cost : -1; // disconnected
}

Example 1 — simple

Three nodes. Edges (0,1,1), (1,2,2), (0,2,50). Kruskal takes 1, then 2, skips 50. Cost 3.

Example 2 — every step

Edges (0,1,10), (0,2,6), (0,3,5), (1,3,15), (2,3,4). Sorted: (2,3,4), (0,3,5), (0,2,6), (0,1,10), (1,3,15).

MST weight 19, edges (2,3), (0,3), (0,1).