Pattern 16: Graph Patterns

0. The Template (Copy-Paste Skeleton)

Graphs have six algorithm templates (all spelled out in §3 below) but only one setup step — and that setup is where most interview time is actually lost. Get the adjacency list right first, then pick a template with the decision tree in §2.

// STEP 0 — BUILD THE ADJACENCY LIST (do this before anything else)
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
}

// WEIGHTED version: store {neighbour, weight}
List<int[]>[] wadj = new List[n];
for (int i = 0; i < n; i++) wadj[i] = new ArrayList<>();
for (int[] e : edges) wadj[e[0]].add(new int[]{e[1], e[2]});

// GRID version: no adjacency list at all — neighbours are computed
static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};   // + 4 diagonals if 8-directional

// CYCLE DETECTION IN A DIRECTED GRAPH — DFS with 3 colours (the one template missing below)
// 0 = unvisited (white), 1 = in the current recursion stack (gray), 2 = done (black)
boolean hasCycle(int u, int[] color, List<List<Integer>> adj) {
    color[u] = 1;                                     // enter: mark gray
    for (int v : adj.get(u)) {
        if (color[v] == 1) return true;               // BACK EDGE into the stack ⇒ cycle
        if (color[v] == 0 && hasCycle(v, color, adj)) return true;
    }
    color[u] = 2;                                     // leave: mark black — fully explored
    return false;
}

Pick your template in one question

The question asks for	Template (§3)	Time
fewest steps / edges, unweighted	3.1 BFS	O(V+E)
just reach everything / connectivity / all paths	3.2 DFS	O(V+E)
a valid order given dependencies	3.3 Topological Sort (Kahn’s)	O(V+E)
grouping, “are these connected”, cycle in an undirected graph	3.4 Union-Find	~O(α(n))
cheapest path, non-negative weights	3.5 Dijkstra	O((V+E) log V)
negative weights, or “does a negative cycle exist”	3.6 Bellman-Ford	O(V·E)
cycle in a directed graph	3-colour DFS (above) or Kahn’s count	O(V+E)
edge weights are only 0 and 1	0-1 BFS: `Deque`, `offerFirst` for 0, `offerLast` for 1	O(V+E)
all-pairs shortest paths, small V	Floyd-Warshall (triple loop)	O(V³)

The four setup mistakes that cost real interviews

Adding both directions on a directed graph (or forgetting the second direction on an undirected one). Read the problem statement twice before you type the build loop.
Marking visited on dequeue instead of enqueue in BFS — the queue balloons to O(E) and counters double-count. Mark when you add.
Treating a grid as needing an adjacency list. It doesn’t — DIRS plus a bounds check is the adjacency. Building the list wastes O(m·n) memory and a lot of clock.
Recursive DFS on a 10^5-node graph → StackOverflowError. Switch to BFS or an explicit Deque stack, and say why.

Comparator note

Use Integer.compare(a[1], b[1]) in the Dijkstra PriorityQueue, not a[1] - b[1] — subtraction overflows once distances approach Integer.MAX_VALUE, which is exactly what Arrays.fill(dist, Integer.MAX_VALUE) puts there.

1. Pattern Identification & Logic

How to Identify (Interview Triggers)

Nodes + edges (explicit or implicit — e.g., 2-D grid where each cell is a node)
“Connected components”, “shortest path”, “reachable”, “is it connected”
“Course schedule / dependencies / build order” → topological sort
“Friend circles”, “redundant connection”, “is it a tree” → Union-Find
“Min cost / time to travel” with non-negative weights → Dijkstra
“Cells flowing to ocean”, “all paths from A to B”, “flood fill” → BFS / DFS on grid
“Cycle detection”

The Six Core Sub-Patterns

Sub-Pattern	Use When	Time	Space
BFS	Unweighted shortest path, level info	O(V+E)	O(V)
DFS	Connectivity, path existence, traversal order	O(V+E)	O(V)
Topological Sort	Order tasks with dependencies; cycle detection (directed)	O(V+E)	O(V)
Union-Find (DSU)	Dynamic connectivity, cycle detection (undirected), grouping	~O(α(N)) per op	O(V)
Dijkstra	Single-source shortest path, non-negative weights	O((V+E) log V)	O(V)
Bellman-Ford	SSSP with negative edges; detect negative cycle	O(V·E)	O(V)

2. The Master Decision Tree

GRAPH PROBLEM
│
├─ Is the graph weighted?
│  ├─ NO  →  BFS for shortest path (each edge = 1 step)
│  └─ YES →
│     ├─ All weights ≥ 0?            → Dijkstra
│     ├─ Negative weights possible?  → Bellman-Ford
│     └─ All-pairs shortest paths?   → Floyd-Warshall (V³)
│
├─ Need ORDER (dependencies)?
│  └─ Topological Sort (Kahn's BFS or DFS post-order)
│
├─ Need to know IF connected / group elements?
│  └─ Union-Find (a.k.a. DSU)
│
├─ Need to visit everything?
│  ├─ Iteratively (avoid deep stack)  → BFS or iterative DFS
│  └─ With path tracking / recursion  → DFS
│
├─ Detect cycle?
│  ├─ Directed graph    → DFS color states (white/gray/black) OR Kahn's count
│  └─ Undirected graph  → Union-Find OR DFS with parent tracking
│
└─ Grid problem?
    └─ Treat each cell as a node; 4-/8-directional neighbors
       ├─ Count components / flood fill → DFS or BFS
       └─ Shortest path / BFS levels     → BFS

3. The Six Universal Templates

3.1 BFS (Shortest Path in Unweighted Graph)

int bfs(int start, int target, List<List<Integer>> adj) {
    Queue<Integer> q = new ArrayDeque<>();
    boolean[] visited = new boolean[adj.size()];
    q.offer(start);
    visited[start] = true;
    int level = 0;
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            int node = q.poll();
            if (node == target) return level;
            for (int next : adj.get(node)) {
                if (!visited[next]) { visited[next] = true; q.offer(next); }
            }
        }
        level++;
    }
    return -1;   // unreachable
}

3.2 DFS (Recursive Traversal)

void dfs(int node, boolean[] visited, List<List<Integer>> adj) {
    if (visited[node]) return;
    visited[node] = true;
    for (int next : adj.get(node)) dfs(next, visited, adj);
}

3.3 Topological Sort (Kahn’s BFS — also detects cycles)

int[] indegree = new int[n];
for (int[] e : edges) indegree[e[1]]++;
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indegree[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 (--indegree[v] == 0) q.offer(v);
}
return order.size() == n ? order : Collections.emptyList(); // empty → cycle

3.4 Union-Find (DSU)

class DSU {
    int[] parent, rank;
    int components;
    DSU(int n) {
        parent = new int[n]; rank = new int[n]; components = n;
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);   // path compression
        return parent[x];
    }
    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        // union by rank
        if (rank[ra] < rank[rb]) { parent[ra] = rb; }
        else if (rank[ra] > rank[rb]) { parent[rb] = ra; }
        else { parent[rb] = ra; rank[ra]++; }
        components--;
        return true;
    }
}

3.5 Dijkstra (Min-Heap)

int[] dijkstra(int n, List<int[]>[] adj, int src) {  // adj[u]: list of {v, w}
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> 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 entry
        for (int[] nb : adj[u]) {
            int v = nb[0], w = nb[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{v, dist[v]});
            }
        }
    }
    return dist;
}

3.6 Bellman-Ford (Detects Negative Cycles)

int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
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] != Integer.MAX_VALUE && dist[u] + w < dist[v]) dist[v] = dist[u] + w;
    }
// One more pass: any update ⇒ negative cycle

4. Cycle Detection Quick Reference

Graph Type	Recommended Method
Directed, want any cycle	DFS with `color[]` (white/gray/black) — back-edge = cycle
Directed, also need topo order	Kahn’s: if `order.size() < n` ⇒ cycle exists
Undirected, want any cycle	Union-Find — `union` returns false ⇒ cycle
Undirected, prefer DFS	DFS with parent — visiting non-parent visited node = cycle

5. Java Architecture Insights

Adjacency list is the default representation: List<List<Integer>> adj or List<int[]>[] adj.
Prefer arrays of primitives (int[], boolean[]) for visited/indegree/dist — much faster than Set<Integer> / Map<Integer,Integer>.
Use ArrayDeque over LinkedList for BFS queues — faster, but forbids nulls.
For Dijkstra, the “lazy deletion” check if (d > dist[u]) continue; is critical — without it, popping a stale (longer) entry wastes work.
For huge graphs, build the adjacency list once in O(V+E). Re-scanning the edge list inside the search loop kills performance.
Recursion depth limit: Java’s default stack handles ~10^4 frames. For deeper graphs, convert DFS to iterative using an explicit Deque<Frame>.

6. Mental Model & Visualization

BFS expanding levels

Level 0:        [S]
Level 1:    [A] [B] [C]
Level 2: [D][E][F] [G][H]

DFS exploring deep

S → A → A1 → A1a (backtrack) → A1b ...
            → A2
        B (visited later)

Union-Find tree (after several unions)

root: 3
   ├── 1 ── 0
   └── 2 ── 5
            └── 4
find(4): walks 4 → 5 → 2 → 3 → 3   (path compression collapses next find to O(1))

7. Curated Problem Lists

Commonly Asked (Bread & Butter)

LC #	Problem	Sub-Pattern	Difficulty
200	Number of Islands	DFS / BFS	Medium
133	Clone Graph	DFS / BFS	Medium
207	Course Schedule	Topo Sort	Medium
210	Course Schedule II	Topo Sort	Medium
547	Number of Provinces	Union-Find / DFS	Medium
994	Rotting Oranges	Multi-source BFS	Medium

FAANG “Aha!” Level

LC #	Problem	Sub-Pattern	Difficulty
417	Pacific Atlantic Water Flow	Reverse Multi-source DFS	Medium
269	Alien Dictionary	Topo Sort	Hard
261	Graph Valid Tree	Union-Find	Medium
323	Number of Connected Components	Union-Find	Medium
743	Network Delay Time	Dijkstra	Medium
787	Cheapest Flights Within K Stops	Bellman-Ford / BFS	Medium
684	Redundant Connection	Union-Find	Medium
1192	Critical Connections (Bridges)	Tarjan’s DFS	Hard
332	Reconstruct Itinerary	Hierholzer (Eulerian)	Hard
685	Redundant Connection II	Union-Find + cases	Hard

8. Time & Space Complexity Cheat Sheet

Algorithm	Time	Space	Notes
BFS / DFS	(O(V + E))	(O(V))	Standard traversal
Topological Sort	(O(V + E))	(O(V))	Kahn’s or DFS post-order
Union-Find	(O(α(N))) per op	(O(V))	α inverse Ackermann — effectively O(1)
Dijkstra	(O((V+E) \log V))	(O(V))	Min-heap; non-negative weights only
Bellman-Ford	(O(V \cdot E))	(O(V))	Handles negative weights
Floyd-Warshall	(O(V^3))	(O(V^2))	All-pairs
Tarjan (SCC/Bridges)	(O(V+E))	(O(V))	DFS with discovery / low times

Pattern 16: Graph Patterns (BFS / DFS / Topological Sort / Union-Find / Dijkstra)