Graphs — Complete Guide: BFS, DFS, Shortest Paths & Advanced Algorithms

Everything about graphs from scratch — representation, BFS, DFS, cycle detection, topological sort, Dijkstra, Bellman-Ford, Floyd-Warshall, Prim, Kruskal, SCC, bridges, articulation points, and every pattern you need to crack any graph interview.

What even is a graph? — A Beginner's Story

Imagine you are looking at Google Maps. Every intersection in the city is a node. Every road connecting two intersections is an edge. The whole city road network is a graph. Now you want to find the shortest route from your home to the airport — that is a graph problem.

Or think about Instagram: every user is a node. When you follow someone, that creates a directed edge (you → them). Finding "people you may know" (friends of friends) is a graph traversal problem. Even your college course prerequisites form a graph — a directed edge from Course A to Course B means "you must complete A before taking B."

A graph is literally everywhere. Once you learn to see graphs, you will recognize them in almost every medium-to-hard interview problem.

The 3 questions to ask for ANY graph problem

Directed or Undirected? (one-way streets vs two-way roads)
Weighted or Unweighted? (do edges have different costs/distances?)
What is a node? What is an edge? (always define this first — grids are graphs where cells are nodes!)

Part 1 — Fundamentals & Representation

Vocabulary at a Glance

Term	Meaning	Real-World Example
Directed / Undirected	Edges have direction (A→B) or go both ways (A↔B)	Twitter follows (directed) vs Facebook friends (undirected)
Weighted	Each edge has a cost/distance	Roads with different travel times
Degree	Number of edges touching a node	How many friends a person has
Path	A sequence of nodes connected by edges	A route on a map
Cycle	A path that starts and ends at the same node	A circular road loop
DAG	Directed Acyclic Graph — directed, no cycles	Course prerequisites (no circular dependencies)
Connected	Every node reachable from every other (undirected)	A fully connected social network
Tree	Connected, undirected, no cycles — exactly V-1 edges	A company org chart

How to Store a Graph — Adjacency List vs Matrix

Before writing any traversal code, you must choose how to store the graph. There are two main options:

	Adjacency List	Adjacency Matrix
Storage	O(V + E)	O(V²)
Check if edge u→v exists	O(degree of u)	O(1)
List all neighbors of u	O(degree of u)	O(V)
Best for	Sparse graphs (few edges) — most interview graphs	Dense graphs (many edges)
Looks like	`adj[u] = [v1, v2, v3]`	`matrix[u][v] = 1 if edge exists`

Rule of thumb: Use an adjacency list for almost every interview problem. Use a matrix only when the problem says "the graph has V nodes and you are given a V×V matrix."

Adjacency List (your default — O(V+E) space)

Python

from collections import defaultdict

# Unweighted undirected
adj = defaultdict(list)
adj[0].append(1); adj[1].append(0)
adj[1].append(2); adj[2].append(1)

# Weighted: store (neighbor, weight)
adj[0].append((1, 5))   # edge 0→1 with weight 5

# Build from input
n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)   # remove for directed

Java

// Java adjacency list
import java.util.*;

List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
adj.get(0).add(1); adj.get(1).add(0);   // undirected

// Weighted: List<List<int[]>> where int[] = {neighbor, weight}
List<List<int[]>> wAdj = new ArrayList<>();
for (int i = 0; i < n; i++) wAdj.add(new ArrayList<>());
wAdj.get(0).add(new int[]{1, 5});   // edge 0→1, weight 5

// Build from Scanner input
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
for (int i = 0; i < m; i++) {
    int u = sc.nextInt(), v = sc.nextInt();
    graph.get(u).add(v);
    graph.get(v).add(u);   // remove for directed
}

C++

#include <bits/stdc++.h>
using namespace std;

// Unweighted undirected
vector<vector<int>> adj(n);
adj[0].push_back(1); adj[1].push_back(0);

// Weighted: vector<vector<pair<int,int>>>
vector<vector<pair<int,int>>> wadj(n);
wadj[0].push_back({1, 5});   // edge 0→1, weight 5

// Build from input
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
    int u, v; cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);   // remove for directed
}

Part 2 — BFS (Breadth-First Search)

Why We Need BFS & How it Works

When searching a graph, if we want to find the shortest path (the minimum number of steps) in an unweighted network (where every edge has the same cost, like a grid map or a friend connection network), we need an algorithm that explores nodes level by level, radiating outward like ripples on a pond.

If we used DFS, we might wander deep down a single path, finding a valid route, but it could be a long detour. BFS guarantees that the first time we visit a node, we have found the absolute shortest path to it.

How to Approach (The Queue Mechanism)

BFS uses a First-In, First-Out (FIFO) queue to manage the frontier of exploration:

Initialize: Push the starting node into the queue and mark it visited. Set its distance to 0.
Process: While the queue is not empty:
- Pop the front node.
- Iterate through its neighbors.
- For each unvisited neighbor:
  - Mark it visited immediately (doing this on enqueue is crucial to prevent the same node from being pushed multiple times).
  - Calculate its distance: dist[neighbor] = dist[node] + 1.
  - Push the neighbor into the queue.

When to Use BFS

Shortest Path / Minimum Hops: Finding the shortest route on a map, grid, or unweighted network.
- LeetCode Link: LeetCode 1091: Shortest Path in Binary Matrix
Minimum Moves to Solve a Game: E.g., sliding puzzle solvers or string transformation challenges.
- LeetCode Link: LeetCode 127: Word Ladder
Multi-Source Shortest Path: Finding the distance from multiple sources simultaneously.
- LeetCode Link: LeetCode 994: Rotting Oranges

Watch BFS run

Before the code: watch the queue drive the traversal. Visited nodes turn green, the frontier waits in amber, and the highlighted edges form the BFS tree — shortest paths by hop count. Try different start nodes.

Breadth-first searchtime O(V + E)space O(V)

queue:A

1/17BFS from A: visit in rings of increasing distance. A queue (FIFO) makes “closest first” automatic.

start node

The #1 BFS Bug — Mark visited on ENQUEUE, not dequeue

Always mark a node visited when you add it to the queue. If you mark on dequeue, the same node enters the queue multiple times — wrong distances and potential infinite loops.

Complete BFS — distance from source

Python

from collections import deque

def bfs(adj, start, n):
    dist = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        node = q.popleft()
        for nb in adj[node]:
            if dist[nb] == -1:
                dist[nb] = dist[node] + 1
                q.append(nb)        # ✅ mark visited ON ENQUEUE
    return dist

Java

int[] bfs(List<List<Integer>> adj, int start, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, -1);
    dist[start] = 0;
    Queue<Integer> q = new ArrayDeque<>();
    q.offer(start);
    while (!q.isEmpty()) {
        int node = q.poll();
        for (int nb : adj.get(node)) {
            if (dist[nb] == -1) {
                dist[nb] = dist[node] + 1;
                q.offer(nb);
            }
        }
    }
    return dist;
}

C++

vector<int> bfs(vector<vector<int>>& adj, int start, int n) {
    vector<int> dist(n, -1);
    dist[start] = 0;
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        int node = q.front(); q.pop();
        for (int nb : adj[node]) {
            if (dist[nb] == -1) {
                dist[nb] = dist[node] + 1;
                q.push(nb);
            }
        }
    }
    return dist;
}

BFS with path reconstruction

BFS hands you the shortest distance, but interviews usually want the shortest path — the actual sequence of nodes. The trick is one extra array: when you first reach a node, record which node you came from (prev). Because BFS reaches every node by a shortest route, following those prev pointers backward from the destination — then reversing — rebuilds a shortest path.

Reach for it when the problem asks for "the path / the sequence of moves / the shortest transformation" (word ladder, knight's moves, a maze route), not just the length.

Python

def bfs_path(adj, start, end, n):
    prev = [-1] * n
    visited = [False] * n
    visited[start] = True
    q = deque([start])
    while q:
        node = q.popleft()
        if node == end: break
        for nb in adj[node]:
            if not visited[nb]:
                visited[nb] = True
                prev[nb] = node
                q.append(nb)
    if not visited[end]: return []
    path, cur = [], end
    while cur != -1:
        path.append(cur); cur = prev[cur]
    return path[::-1]

Java

List<Integer> bfsPath(List<List<Integer>> adj, int start, int end, int n) {
    int[] prev = new int[n];
    Arrays.fill(prev, -1);
    boolean[] visited = new boolean[n];
    visited[start] = true;
    Queue<Integer> q = new ArrayDeque<>();
    q.offer(start);
    while (!q.isEmpty()) {
        int node = q.poll();
        if (node == end) break;
        for (int nb : adj.get(node)) {
            if (!visited[nb]) {
                visited[nb] = true;
                prev[nb] = node;
                q.offer(nb);
            }
        }
    }
    if (!visited[end]) return new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    for (int cur = end; cur != -1; cur = prev[cur]) path.add(cur);
    Collections.reverse(path);
    return path;
}

C++

vector<int> bfsPath(vector<vector<int>>& adj, int start, int end, int n) {
    vector<int> prev(n, -1);
    vector<bool> visited(n, false);
    visited[start] = true;
    queue<int> q; q.push(start);
    while (!q.empty()) {
        int node = q.front(); q.pop();
        if (node == end) break;
        for (int nb : adj[node]) {
            if (!visited[nb]) {
                visited[nb] = true;
                prev[nb] = node;
                q.push(nb);
            }
        }
    }
    if (!visited[end]) return {};
    vector<int> path;
    for (int cur = end; cur != -1; cur = prev[cur]) path.push_back(cur);
    reverse(path.begin(), path.end());
    return path;
}

Multi-source BFS

The problem: find each node's distance to the nearest of many starting points — nearest warehouse, nearest exit, nearest rotting orange. Running a separate BFS from every source would be O(sources × (V+E)), far too slow.

The trick: seed the queue with all sources at distance 0 at once, then run one ordinary BFS. The wavefront now grows from every source simultaneously, so the first time a node is reached it's reached by the closest source — exactly the nearest-source distance, in a single O(V+E) pass. (This is the whole idea behind Rotting Oranges, later in this chapter.)

Python

def multi_source_bfs(adj, sources, n):
    dist = [-1] * n
    q = deque()
    for s in sources:
        dist[s] = 0; q.append(s)
    while q:
        node = q.popleft()
        for nb in adj[node]:
            if dist[nb] == -1:
                dist[nb] = dist[node] + 1
                q.append(nb)
    return dist

Java

int[] multiSourceBFS(List<List<Integer>> adj, List<Integer> sources, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, -1);
    Queue<Integer> q = new ArrayDeque<>();
    for (int s : sources) { dist[s] = 0; q.offer(s); }
    while (!q.isEmpty()) {
        int node = q.poll();
        for (int nb : adj.get(node)) {
            if (dist[nb] == -1) { dist[nb] = dist[node] + 1; q.offer(nb); }
        }
    }
    return dist;
}

C++

vector<int> multiSourceBFS(vector<vector<int>>& adj, vector<int>& sources, int n) {
    vector<int> dist(n, -1);
    queue<int> q;
    for (int s : sources) { dist[s] = 0; q.push(s); }
    while (!q.empty()) {
        int node = q.front(); q.pop();
        for (int nb : adj[node]) {
            if (dist[nb] == -1) { dist[nb] = dist[node] + 1; q.push(nb); }
        }
    }
    return dist;
}

BFS on a 2D grid

A grid is a graph in disguise: every cell is a node, and each cell has edges to its (up to) four orthogonal neighbours. You almost never build an adjacency list for it — you generate neighbours on the fly from a dirs array, skipping anything out of bounds or blocked. That's an implicit graph, and it's the single most common BFS setting in interviews.

Reach for it when you see "shortest path / fewest steps in a maze or grid", flood fill, or "minimum time for X to spread". The traversal is the same BFS — only neighbour generation changes.

Python

def bfs_grid(grid, start_r, start_c):
    rows, cols = len(grid), len(grid[0])
    dist = [[-1]*cols for _ in range(rows)]
    dist[start_r][start_c] = 0
    q = deque([(start_r, start_c)])
    dirs = [(0,1),(0,-1),(1,0),(-1,0)]
    while q:
        r, c = q.popleft()
        for dr, dc in dirs:
            nr, nc = r+dr, c+dc
            if 0<=nr<rows and 0<=nc<cols and dist[nr][nc]==-1 and grid[nr][nc]!='#':
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist

Java

int[][] bfsGrid(char[][] grid, int sr, int sc) {
    int rows = grid.length, cols = grid[0].length;
    int[][] dist = new int[rows][cols];
    for (int[] row : dist) Arrays.fill(row, -1);
    dist[sr][sc] = 0;
    Queue<int[]> q = new ArrayDeque<>();
    q.offer(new int[]{sr, sc});
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int r = cur[0], c = cur[1];
        for (int[] d : dirs) {
            int nr = r+d[0], nc = c+d[1];
            if (nr>=0 && nr<rows && nc>=0 && nc<cols && dist[nr][nc]==-1 && grid[nr][nc]!='#') {
                dist[nr][nc] = dist[r][c] + 1;
                q.offer(new int[]{nr, nc});
            }
        }
    }
    return dist;
}

C++

vector<vector<int>> bfsGrid(vector<vector<char>>& grid, int sr, int sc) {
    int rows = grid.size(), cols = grid[0].size();
    vector<vector<int>> dist(rows, vector<int>(cols, -1));
    dist[sr][sc] = 0;
    queue<pair<int,int>> q; q.push({sr, sc});
    int dirs[][2] = {{0,1},{0,-1},{1,0},{-1,0}};
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (auto& d : dirs) {
            int nr = r+d[0], nc = c+d[1];
            if (nr>=0 && nr<rows && nc>=0 && nc<cols && dist[nr][nc]==-1 && grid[nr][nc]!='#') {
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }
    return dist;
}

Part 3 — DFS (Depth-First Search)

Why We Need DFS & How it Works

Unlike BFS, which explores nodes layer by layer, DFS (Depth-First Search) dives as deep as possible down a single branch before backtracking. Think of it as exploring a maze by walking forward until you hit a dead end, then taking one step back to check other paths.

We need DFS when we want to fully explore paths, check for connectivity (e.g., "is there any path between A and B?"), search for cycles, or do exhaustive searches where the shortest path is not the objective.

How to Approach (The Stack / Recursion Mechanism)

DFS uses a Last-In, First-Out (LIFO) stack, which is naturally managed by the computer's recursion call stack:

Initialize: Start at a node, mark it as visited.
Recurse: For each unvisited neighbor, recursively call DFS on it.
Backtrack: When a node has no unvisited neighbors left, the function returns, "backtracking" to the previous node to check its remaining neighbors.

When to Use DFS

Connected Components: Finding how many disconnected islands or sub-networks exist.
- LeetCode Link: LeetCode 200: Number of Islands
All Paths / Exhaustive Search: Finding all possible routes from start to finish.
- LeetCode Link: LeetCode 797: All Paths From Source to Target
Solving Mazes / Word Searches: Backtracking search in grids.
- LeetCode Link: LeetCode 79: Word Search
Cycle Detection / Topological Sorting: Finding topological orders of tasks.

Watch DFS run

Same graph, same start node as BFS above — but a stack instead of a queue. Compare the shapes: long tendrils instead of expanding rings.

Depth-first searchtime O(V + E)space O(V)

stack:A

1/20DFS from A: dive as deep as possible before backtracking. A stack (LIFO) — or recursion — drives it.

start node

DFS recursive

DFS dives as deep as it can down one path, then backtracks and tries the next branch — and the recursion's call stack does the backtracking for you, which is why DFS is naturally recursive. Each call marks its node visited and recurses into unvisited neighbours.

The count_components helper shows the classic use: start a fresh DFS from every node you haven't seen yet. Each fresh start floods one entire connected blob, so the number of starts equals the number of connected components.

Reach for DFS when the question is about connectivity, components, "does a path exist", flood fill, or exploring all of something — anywhere you don't need the shortest distance (that's BFS's job).

Python

def dfs(adj, node, visited):
    visited[node] = True
    for nb in adj[node]:
        if not visited[nb]:
            dfs(adj, nb, visited)

def count_components(adj, n):
    visited = [False] * n
    count = 0
    for i in range(n):
        if not visited[i]:
            dfs(adj, i, visited)
            count += 1
    return count

Java

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

int countComponents(List<List<Integer>> adj, int n) {
    boolean[] visited = new boolean[n];
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) { dfs(adj, i, visited); count++; }
    }
    return count;
}

C++

void dfs(vector<vector<int>>& adj, int node, vector<bool>& visited) {
    visited[node] = true;
    for (int nb : adj[node])
        if (!visited[nb]) dfs(adj, nb, visited);
}

int countComponents(vector<vector<int>>& adj, int n) {
    vector<bool> visited(n, false);
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) { dfs(adj, i, visited); count++; }
    }
    return count;
}

DFS iterative (for large graphs, avoids recursion limit)

Recursive DFS is clean, but Python caps recursion at ~1000 frames — a graph with a long chain of 10⁵ nodes overflows it with a RecursionError (Java/C++ blow the stack too). The fix: replace the hidden call stack with an explicit stack that does exactly the same job.

One subtlety: check visited when you pop, not when you push — the same node can be pushed several times before it's first processed. Pop a node, skip it if it's already done, otherwise mark it and push its neighbours.

Python

def dfs_iterative(adj, start, n):
    visited = [False] * n
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        if visited[node]: continue
        visited[node] = True
        order.append(node)
        for nb in adj[node]:
            if not visited[nb]: stack.append(nb)
    return order

Java

List<Integer> dfsIterative(List<List<Integer>> adj, int start, int n) {
    boolean[] visited = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);
    List<Integer> order = new ArrayList<>();
    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (visited[node]) continue;
        visited[node] = true;
        order.add(node);
        for (int nb : adj.get(node))
            if (!visited[nb]) stack.push(nb);
    }
    return order;
}

C++

vector<int> dfsIterative(vector<vector<int>>& adj, int start, int n) {
    vector<bool> visited(n, false);
    stack<int> st;
    st.push(start);
    vector<int> order;
    while (!st.empty()) {
        int node = st.top(); st.pop();
        if (visited[node]) continue;
        visited[node] = true;
        order.push_back(node);
        for (int nb : adj[node])
            if (!visited[nb]) st.push(nb);
    }
    return order;
}

Part 4 — Cycle Detection

Why and When We Need Cycle Detection

Cycle detection answers the question: "Are there circular loops in this network?"

Undirected Cycle Detection: Used to verify if a graph is a tree (a tree is connected and has no cycles) or to find redundant edges.
- LeetCode Link: LeetCode 261: Graph Valid Tree
Directed Cycle Detection: Crucial for scheduling tasks (deadlocks), compiler build dependencies (circular imports), or job execution orders.
- LeetCode Link: LeetCode 207: Course Schedule

Cycle in an Undirected Graph (DFS + Parent Check)

How to Approach

In an undirected graph, an edge connects two nodes in both directions ($u \leftrightarrow v$). If we search neighbor lists blindly, when we are at node $v$, we will see node $u$ (our predecessor) as a neighbor. This is not a cycle; it is just the edge we walked in on.

To detect real cycles, we must pass a parent variable along our traversal:

Perform DFS from the starting node.
For each neighbor:
- If the neighbor is unvisited, recursively run DFS, passing the current node as the new parent.
- If the neighbor is already visited and is NOT our parent, we have found a second way to reach this node. This represents a loop $ o$ Cycle detected!

Python

def has_cycle_undirected(adj, n):
    visited = [False] * n
    def dfs(node, parent):
        visited[node] = True
        for nb in adj[node]:
            if not visited[nb]:
                if dfs(nb, node): return True
            elif nb != parent:   # visited AND not parent = cycle!
                return True
        return False
    for i in range(n):
        if not visited[i]:
            if dfs(i, -1): return True
    return False

Java

boolean hasCycleUndirected(List<List<Integer>> adj, int n) {
    boolean[] visited = new boolean[n];
    for (int i = 0; i < n; i++)
        if (!visited[i] && dfsCycle(adj, i, -1, visited)) return true;
    return false;
}

boolean dfsCycle(List<List<Integer>> adj, int node, int parent, boolean[] visited) {
    visited[node] = true;
    for (int nb : adj.get(node)) {
        if (!visited[nb]) { if (dfsCycle(adj, nb, node, visited)) return true; }
        else if (nb != parent) return true;
    }
    return false;
}

C++

bool dfsCycleU(vector<vector<int>>& adj, int node, int parent, vector<bool>& visited) {
    visited[node] = true;
    for (int nb : adj[node]) {
        if (!visited[nb]) { if (dfsCycleU(adj, nb, node, visited)) return true; }
        else if (nb != parent) return true;
    }
    return false;
}

bool hasCycleUndirected(vector<vector<int>>& adj, int n) {
    vector<bool> visited(n, false);
    for (int i = 0; i < n; i++)
        if (!visited[i] && dfsCycleU(adj, i, -1, visited)) return true;
    return false;
}

Cycle in a Directed Graph (DFS + 3-Coloring)

Why the Parent Check Fails

In a directed graph, edges have directions ($u \to v$ does not mean $v \to u$). Just because we visit a node that has already been visited doesn't mean there is a cycle. For example, in a diamond-shaped DAG ($A \to B \to D$, and $A \to C \to D$), we can visit $D$ twice, but there is no cycle! A cycle only exists if we find a back edge — an edge that points back to an ancestor node that is still on our active recursion stack.

How to Approach (The 3-Color Scheme)

We track exploration states using three status states (colors):

White (0): Unvisited.
Gray (1): In-progress. The node is currently on the active recursion path (we are exploring its children).
Black (2): Fully processed. We have finished exploring this node and all of its descendants.

3-Color Visual Mental Model — Burn This Into Memory

Imagine painting nodes as you explore them:

White (0) → Gray (1) → Black (2)
  │            │
  │            └─ GRAY neighbor found? → 🚨 CYCLE! (back edge to active ancestor)
  └─ first visit

Example — Graph: A → B → C → A (cycle exists)

Step 1: Visit A  → color A = GRAY
Step 2: Visit B  → color B = GRAY
Step 3: Visit C  → color C = GRAY
Step 4: C's neighbor = A, and A is GRAY → 🚨 CYCLE DETECTED!

Example — Graph: A → B → D, A → C → D (diamond, NO cycle)

Step 1: Visit A = GRAY, Visit B = GRAY
Step 2: Visit D = GRAY, D has no neighbors → D = BLACK
Step 3: B = BLACK. Back to A, visit C = GRAY
Step 4: C's neighbor D is BLACK → skip (already fully processed, not a back edge)
Step 5: C = BLACK. A = BLACK. → No cycle!

Key insight: A Gray neighbor = you found a node that is your ancestor and still being explored = back edge = cycle. A Black neighbor is safe — it's from a completely finished branch.

Algorithm Steps:

Start DFS on a White node and color it Gray.
Explore its neighbors:
- If a neighbor is Gray, we have hit an active ancestor $\to$ Cycle detected!
- If a neighbor is White, recursively explore it.
- If a neighbor is Black, ignore it (it belongs to a fully processed branch).
Once all neighbors are explored, mark the current node Black and return.

Python

def has_cycle_directed(adj, n):
    # 0=unvisited, 1=in-progress (gray), 2=done (black)
    color = [0] * n
    def dfs(node):
        color[node] = 1
        for nb in adj[node]:
            if color[nb] == 1: return True   # back edge = cycle
            if color[nb] == 0 and dfs(nb): return True
        color[node] = 2
        return False
    for i in range(n):
        if color[i] == 0 and dfs(i): return True
    return False

Java

boolean hasCycleDirected(List<List<Integer>> adj, int n) {
    int[] color = new int[n];  // 0=white, 1=gray, 2=black
    for (int i = 0; i < n; i++)
        if (color[i] == 0 && dfsCycleD(adj, i, color)) return true;
    return false;
}

boolean dfsCycleD(List<List<Integer>> adj, int node, int[] color) {
    color[node] = 1;
    for (int nb : adj.get(node)) {
        if (color[nb] == 1) return true;
        if (color[nb] == 0 && dfsCycleD(adj, nb, color)) return true;
    }
    color[node] = 2;
    return false;
}

C++

bool dfsCycleD(vector<vector<int>>& adj, int node, vector<int>& color) {
    color[node] = 1;
    for (int nb : adj[node]) {
        if (color[nb] == 1) return true;
        if (color[nb] == 0 && dfsCycleD(adj, nb, color)) return true;
    }
    color[node] = 2;
    return false;
}

bool hasCycleDirected(vector<vector<int>>& adj, int n) {
    vector<int> color(n, 0);
    for (int i = 0; i < n; i++)
        if (color[i] == 0 && dfsCycleD(adj, i, color)) return true;
    return false;
}

Part 5 — Topological Sort (DAGs)

Why We Need Topological Sort

Imagine you are installing package dependencies or choosing the order to take college courses. If course A is a prerequisite for course B, you must take A before B. A topological sort is a linear ordering of vertices in a directed graph such that for every directed edge $u o v$, node $u$ comes before $v$ in the ordering.

Constraints & Invariants

A topological sort is only possible if the graph is a DAG (Directed Acyclic Graph). If there is a cycle (e.g., A depends on B, B depends on C, and C depends on A), no valid order can exist.
The sort is not unique. A graph can have multiple valid topological orders (e.g. if A and B have no prerequisites, you can take A first or B first).

Kahn's Algorithm (BFS-based — preferred)

How to Approach

Kahn's algorithm uses a greedy BFS approach by tracking in-degrees (the number of incoming edges to a node, which represents the number of active dependencies/prerequisites):

Calculate In-degrees: Count the incoming edges for each node.
Find Starting Frontier: Push all nodes with in-degree 0 (no prerequisites) into a queue.
Process: While the queue is not empty:
- Pop a node and append it to our sorted order list.
- For each neighbor of this node (nodes that depend on it):
  - Decrement their in-degree by 1 (simulates satisfying the dependency).
  - If a neighbor's in-degree drops to 0, push it to the queue (it is now unblocked).
Cycle Verification: If the sorted list contains all $V$ vertices, we have a valid sort. If it is shorter, some nodes are stuck in a dependency loop $ o$ a cycle exists.

When to Use Topological Sort

Dependency resolution (package managers, build order).
Task scheduling under prerequisites constraints.
- LeetCode Link: LeetCode 210: Course Schedule II

Python

from collections import deque

def topological_sort_kahn(adj, n):
    indegree = [0] * n
    for u in range(n):
        for v in adj[u]: indegree[v] += 1
    q = deque([i for i in range(n) if indegree[i] == 0])
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nb in adj[node]:
            indegree[nb] -= 1
            if indegree[nb] == 0: q.append(nb)
    return order if len(order) == n else []   # [] → cycle exists

Java

List<Integer> topoKahn(List<List<Integer>> adj, int n) {
    int[] indegree = new int[n];
    for (int u = 0; u < n; u++) for (int v : adj.get(u)) indegree[v]++;
    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 node = q.poll();
        order.add(node);
        for (int nb : adj.get(node))
            if (--indegree[nb] == 0) q.offer(nb);
    }
    return order.size() == n ? order : new ArrayList<>();
}

C++

vector<int> topoKahn(vector<vector<int>>& adj, int n) {
    vector<int> indegree(n, 0);
    for (int u = 0; u < n; u++) for (int v : adj[u]) indegree[v]++;
    queue<int> q;
    for (int i = 0; i < n; i++) if (indegree[i] == 0) q.push(i);
    vector<int> order;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        order.push_back(node);
        for (int nb : adj[node]) if (--indegree[nb] == 0) q.push(nb);
    }
    return (int)order.size() == n ? order : vector<int>{};
}

DFS-based Topological Sort (Post-Order + Reverse)

Kahn's Algorithm is BFS-based and is great for detecting cycles. But there is a second, equally important approach — DFS post-order topological sort. This is the one that appears naturally when you study how compilers resolve dependencies.

How to Approach (The Intuition)

When you finish DFS on a node (all its descendants have been explored), you push it to a stack. Since a node finishes after all nodes it depends on, reversing the finish order gives a valid topological order.

Think of it this way: if you must finish course A before B, then DFS finishes A after B (because when exploring from A, you go deep into B first). Push to stack on finish → stack has B on top of A → reverse = A before B. ✅

Python

def topological_sort_dfs(adj, n):
    visited = [False] * n
    stack = []       # nodes pushed AFTER all descendants are done

    def dfs(node):
        visited[node] = True
        for nb in adj[node]:
            if not visited[nb]:
                dfs(nb)
        stack.append(node)   # push AFTER exploring all neighbors

    for i in range(n):
        if not visited[i]:
            dfs(i)

    return stack[::-1]   # reverse = topological order

Java

List<Integer> topoSortDFS(List<List<Integer>> adj, int n) {
    boolean[] visited = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++)
        if (!visited[i]) dfsTopo(adj, i, visited, stack);

    List<Integer> order = new ArrayList<>();
    while (!stack.isEmpty()) order.add(stack.pop());
    return order;
}

void dfsTopo(List<List<Integer>> adj, int node, boolean[] visited, Deque<Integer> stack) {
    visited[node] = true;
    for (int nb : adj.get(node))
        if (!visited[nb]) dfsTopo(adj, nb, visited, stack);
    stack.push(node);   // push AFTER all neighbors are done
}

C++

void dfsTopo(vector<vector<int>>& adj, int node, vector<bool>& visited, stack<int>& st) {
    visited[node] = true;
    for (int nb : adj[node])
        if (!visited[nb]) dfsTopo(adj, nb, visited, st);
    st.push(node);   // push AFTER exploring all descendants
}

vector<int> topoSortDFS(vector<vector<int>>& adj, int n) {
    vector<bool> visited(n, false);
    stack<int> st;
    for (int i = 0; i < n; i++)
        if (!visited[i]) dfsTopo(adj, i, visited, st);
    vector<int> order;
    while (!st.empty()) { order.push_back(st.top()); st.pop(); }
    return order;
}

Kahn's (BFS) vs DFS Topological Sort — Which to Use?

	Kahn's Algorithm (BFS)	DFS Post-Order
Cycle detection	✅ Built-in (output size < n = cycle exists)	❌ Need separate cycle check
Style	Iterative (no recursion limit)	Recursive (watch stack depth)
When preferred	When you also need to detect if a cycle exists	When you are already doing DFS for other reasons
Interview pick	✅ Usually preferred — cleaner to explain	Good to know as a second approach

Course Schedule (LeetCode 207)

Why and How to Approach

In the Course Schedule problem, we are given a number of courses and a list of prerequisites. For example, [0, 1] means to take course 0, you must first take course 1. This is a classic dependency problem.

We can model this as a Directed Graph:

Nodes: The courses (labeled 0 to numCourses - 1).
Edges: A prerequisite [a, b] represents a directed edge b -> a (course b must be taken before course a).
Objective: Determine if it is possible to finish all courses. This is equivalent to checking if the directed graph contains no cycles (i.e. is it a DAG?).

We can solve this using either Kahn's Algorithm (BFS) or 3-Color Cycle Detection (DFS). Since Kahn's algorithm naturally counts how many courses we are able to take without getting stuck, we can just check if our completed course count equals numCourses.

Let's look at the implementations:

Python

def can_finish(numCourses, prerequisites):
    adj = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    for a, b in prerequisites:
        adj[b].append(a); indegree[a] += 1
    q = deque([i for i in range(numCourses) if indegree[i] == 0])
    taken = 0
    while q:
        node = q.popleft(); taken += 1
        for nb in adj[node]:
            indegree[nb] -= 1
            if indegree[nb] == 0: q.append(nb)
    return taken == numCourses

Java

boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
    int[] indegree = new int[numCourses];
    for (int[] p : prerequisites) { adj.get(p[1]).add(p[0]); indegree[p[0]]++; }
    Queue<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) q.offer(i);
    int taken = 0;
    while (!q.isEmpty()) {
        int node = q.poll(); taken++;
        for (int nb : adj.get(node)) if (--indegree[nb] == 0) q.offer(nb);
    }
    return taken == numCourses;
}

C++

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(numCourses);
    vector<int> indegree(numCourses, 0);
    for (auto& p : prerequisites) { adj[p[1]].push_back(p[0]); indegree[p[0]]++; }
    queue<int> q;
    for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) q.push(i);
    int taken = 0;
    while (!q.empty()) {
        int node = q.front(); q.pop(); taken++;
        for (int nb : adj[node]) if (--indegree[nb] == 0) q.push(nb);
    }
    return taken == numCourses;
}

Part 6 — Shortest Paths

Scenario	Algorithm	Complexity
Unweighted	BFS	O(V+E)
Weighted, non-negative, single source	Dijkstra	O((V+E) log V)
Weighted, negative edges, single source	Bellman-Ford	O(VE)
All pairs	Floyd-Warshall	O(V³)
DAG (any weights)	Topo sort + relax	O(V+E)
Weights 0 or 1	0-1 BFS (deque)	O(V+E)

Dijkstra's Algorithm

Watch Dijkstra run

Follow the distance table as it tightens: the cheapest unsettled node gets settled (green), its edges relax neighbours (amber = improved, red = no improvement). The greedy choice is safe because weights are non-negative.

Dijkstra — shortest pathstime O((V+E) log V)space O(V)

priority queue:A:0

node	A	B	C	D	E	F	G	H
dist	0	∞	∞	∞	∞	∞	∞	∞

1/19Dijkstra from A: dist[A] = 0, everything else ∞. Always settle the cheapest unsettled node next — greedy works because weights are non-negative.

start node

When you need it: single-source shortest path on a weighted graph with non-negative weights — Google Maps routing, cheapest network path, minimum cost to reach every node.

The intuition: Dijkstra is BFS upgraded with a priority queue. Instead of expanding the nearest node by hop count, it always expands the nearest node by total distance so far, then relaxes its edges — "if going through me is cheaper than your current best, lower your distance."

Why the greedy choice is safe: once the closest unsettled node is pulled from the heap, no other route can ever beat it — any alternative would have to detour through a node that's already farther away, and adding more non-negative edges can't make it cheaper. That's exactly why negative weights break Dijkstra (and send you to Bellman-Ford). The if d > dist[node]: continue line simply skips stale heap entries left over from earlier, larger estimates.

Python

import heapq

def dijkstra(adj, src, n):
    """adj[u] = list of (neighbor, weight). Returns dist array."""
    dist = [float('inf')] * n
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]: continue   # stale entry
        for nb, w in adj[node]:
            nd = dist[node] + w
            if nd < dist[nb]:
                dist[nb] = nd
                heapq.heappush(heap, (nd, nb))
    return [d if d != float('inf') else -1 for d in dist]

Java

int[] dijkstra(List<List<int[]>> adj, int src, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    // PQ stores {distance, node}
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[]{0, src});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], node = cur[1];
        if (d > dist[node]) continue;
        for (int[] edge : adj.get(node)) {
            int nb = edge[0], w = edge[1];
            if (dist[node] + w < dist[nb]) {
                dist[nb] = dist[node] + w;
                pq.offer(new int[]{dist[nb], nb});
            }
        }
    }
    return dist;
}

C++

vector<int> dijkstra(vector<vector<pair<int,int>>>& adj, int src, int n) {
    vector<int> dist(n, INT_MAX);
    dist[src] = 0;
    // min-heap: {distance, node}
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, node] = pq.top(); pq.pop();
        if (d > dist[node]) continue;   // stale
        for (auto [nb, w] : adj[node]) {
            if (dist[node] + w < dist[nb]) {
                dist[nb] = dist[node] + w;
                pq.push({dist[nb], nb});
            }
        }
    }
    return dist;
}

0-1 BFS (weights are only 0 or 1)

When: every edge weight is 0 or 1 (e.g. "a normal move costs 1, a teleport is free"). Dijkstra works, but its log factor is overkill here.

The trick: swap the heap for a plain deque. A 0-weight edge doesn't increase the distance, so push that neighbour to the front (process it immediately, same distance band); a 1-weight edge pushes to the back (next band). The deque stays ordered by distance for free, giving O(V+E) — BFS speed with just enough weight-awareness.

Python

from collections import deque

def bfs_01(adj, src, n):
    dist = [float('inf')] * n
    dist[src] = 0
    dq = deque([src])
    while dq:
        node = dq.popleft()
        for nb, w in adj[node]:
            if dist[node] + w < dist[nb]:
                dist[nb] = dist[node] + w
                if w == 0: dq.appendleft(nb)   # free: process ASAP
                else: dq.append(nb)             # cost: process later
    return dist

Java

int[] bfs01(List<List<int[]>> adj, int src, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    Deque<Integer> dq = new ArrayDeque<>();
    dq.addFirst(src);
    while (!dq.isEmpty()) {
        int node = dq.pollFirst();
        for (int[] edge : adj.get(node)) {
            int nb = edge[0], w = edge[1];
            if (dist[node] + w < dist[nb]) {
                dist[nb] = dist[node] + w;
                if (w == 0) dq.addFirst(nb); else dq.addLast(nb);
            }
        }
    }
    return dist;
}

C++

vector<int> bfs01(vector<vector<pair<int,int>>>& adj, int src, int n) {
    vector<int> dist(n, INT_MAX);
    dist[src] = 0;
    deque<int> dq; dq.push_back(src);
    while (!dq.empty()) {
        int node = dq.front(); dq.pop_front();
        for (auto [nb, w] : adj[node]) {
            if (dist[node] + w < dist[nb]) {
                dist[nb] = dist[node] + w;
                if (w == 0) dq.push_front(nb);
                else dq.push_back(nb);
            }
        }
    }
    return dist;
}

Bellman-Ford (negative edges + cycle detection)

When: the graph has negative edge weights (Dijkstra's greedy assumption fails), or you need to detect a negative cycle — the classic being currency arbitrage, where a loop of trades multiplies money forever.

The intuition: forget cleverness — just relax every edge, n−1 times. After round k, every shortest path that uses at most k edges is already correct; since a shortest path without repeated nodes has at most n−1 edges, n−1 rounds settle them all. (The updated flag lets you stop early once a round changes nothing.)

Negative-cycle check: run one extra round. If anything still improves, a negative cycle exists — you could loop it to push the cost down forever, so no finite shortest path is defined. It's O(V·E), slower than Dijkstra, but that's the price of handling negatives.

Python

def bellman_ford(n, edges, src):
    """edges: list of (u, v, weight)"""
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w; updated = True
        if not updated: break
    # Detect negative cycles
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            dist[v] = float('-inf')
    return dist

Java

int[] bellmanFord(int n, int[][] edges, int src) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    for (int i = 0; i < n - 1; i++) {
        boolean updated = false;
        for (int[] e : edges) {
            if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {
                dist[e[1]] = dist[e[0]] + e[2]; updated = true;
            }
        }
        if (!updated) break;
    }
    for (int[] e : edges)
        if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]])
            dist[e[1]] = Integer.MIN_VALUE;
    return dist;
}

C++

vector<int> bellmanFord(int n, vector<tuple<int,int,int>>& edges, int src) {
    vector<int> dist(n, INT_MAX);
    dist[src] = 0;
    for (int i = 0; i < n - 1; i++) {
        bool updated = false;
        for (auto [u, v, w] : edges) {
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w; updated = true;
            }
        }
        if (!updated) break;
    }
    for (auto [u, v, w] : edges)
        if (dist[u] != INT_MAX && dist[u] + w < dist[v])
            dist[v] = INT_MIN;
    return dist;
}

Floyd-Warshall (All-Pairs Shortest Path)

When: you need the shortest distance between every pair of nodes and the graph is small/dense (V ≤ ~400). One run fills the whole distance matrix.

The intuition: it's a tiny DP over which nodes you're allowed to pass through. The outer loop variable k means "you may now also route through node k." For every pair (i, j), check whether i→k→j beats the best i→j so far. Once k has ranged over all nodes, every pair has considered every possible intermediary, so every entry is optimal.

Mind the loop order: k must be the outermost loop — it's the dimension being unlocked. Three nested loops, ten lines, O(V³) — the easiest shortest-path algorithm to code correctly under pressure.

Python

def floyd_warshall(n, edges):
    INF = float('inf')
    dist = [[INF]*n for _ in range(n)]
    for i in range(n): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)
        dist[v][u] = min(dist[v][u], w)   # remove for directed
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

Java

int[][] floydWarshall(int n, int[][] edges) {
    int INF = (int)1e9;
    int[][] dist = new int[n][n];
    for (int[] row : dist) Arrays.fill(row, INF);
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (int[] e : edges) {
        dist[e[0]][e[1]] = Math.min(dist[e[0]][e[1]], e[2]);
        dist[e[1]][e[0]] = Math.min(dist[e[1]][e[0]], e[2]);
    }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
    return dist;
}

C++

vector<vector<int>> floydWarshall(int n, vector<tuple<int,int,int>>& edges) {
    const int INF = 1e9;
    vector<vector<int>> dist(n, vector<int>(n, INF));
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (auto [u, v, w] : edges) {
        dist[u][v] = min(dist[u][v], w);
        dist[v][u] = min(dist[v][u], w);   // remove for directed
    }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    return dist;
}

Part 7 — Minimum Spanning Trees (MST)

Why Do We Need MST? — A Beginner's Story

Imagine you are a network engineer at Spotify. You have 10 server racks in a data center and you need to connect all of them with ethernet cables so data can travel between any two racks. Each possible cable connection has a different cost (some racks are closer together). You want to connect ALL racks using the minimum total length of cable, with no loops.

This is exactly the Minimum Spanning Tree problem. You want to span (connect) all nodes, minimize the total edge weight, and use exactly n-1 edges (no cycles, because a cycle would mean you paid for a redundant cable).

When to reach for MST:

"Connect all points at minimum cost"
Network design (power grids, fiber optic cables)
Clustering algorithms
Any problem with the phrase "minimum cost to connect everything"

Two greedy algorithms both find it — Kruskal (think in edges) and Prim (think in nodes).

Kruskal's Algorithm (sort edges, use Union-Find)

The intuition: sort every edge cheapest-first, then walk the list adding each edge unless it would form a cycle (its two endpoints are already connected). Union-Find answers "already connected?" in near-O(1). Stop once you've chosen n−1 edges. Greedily taking the cheapest safe edge is provably optimal (the cut property).

Reach for Kruskal when the graph is sparse or you're handed an edge list — it's just sorting plus Union-Find.

Python

def kruskal(n, edges):
    """edges: list of (weight, u, v). Returns (total_weight, mst_edges)."""
    edges.sort()
    parent = list(range(n)); rank = [0] * n
    def find(x):
        if parent[x] != x: parent[x] = find(parent[x])
        return parent[x]
    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry: return False
        if rank[rx] < rank[ry]: rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]: rank[rx] += 1
        return True
    mst_w, mst_edges = 0, []
    for w, u, v in edges:
        if union(u, v):
            mst_w += w; mst_edges.append((u, v, w))
            if len(mst_edges) == n - 1: break
    return mst_w, mst_edges

Java

int kruskal(int n, int[][] edges) {
    Arrays.sort(edges, Comparator.comparingInt(e -> e[0]));
    int[] parent = new int[n], rank = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    int mstWeight = 0, edgeCount = 0;
    for (int[] e : edges) {
        int pu = find(parent, e[1]), pv = find(parent, e[2]);
        if (pu != pv) {
            if (rank[pu] < rank[pv]) { int t = pu; pu = pv; pv = t; }
            parent[pv] = pu;
            if (rank[pu] == rank[pv]) rank[pu]++;
            mstWeight += e[0];
            if (++edgeCount == n - 1) break;
        }
    }
    return mstWeight;
}
int find(int[] parent, int x) {
    return parent[x] == x ? x : (parent[x] = find(parent, parent[x]));
}

C++

struct UnionFind {
    vector<int> parent, rank;
    UnionFind(int n) : parent(n), rank(n, 0) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
        return true;
    }
};

int kruskal(int n, vector<tuple<int,int,int>> edges) {
    sort(edges.begin(), edges.end());
    UnionFind uf(n);
    int mstWeight = 0;
    for (auto [w, u, v] : edges) {
        if (uf.unite(u, v)) {
            mstWeight += w;
            if (--n == 1) break;   // n-1 edges picked
        }
    }
    return mstWeight;
}

Prim's Algorithm (grow MST node by node)

The intuition: grow one tree outward from a starting node. Keep a min-heap of all edges crossing from "in the tree" to "not yet in the tree," and repeatedly add the cheapest edge that reaches a new node. It's Dijkstra's shape, but you compare a single edge weight rather than a total distance from the source.

Kruskal vs Prim: Kruskal sorts all edges (great for sparse graphs / edge lists); Prim grows from a node with a heap (great for dense graphs / adjacency lists). Both produce an optimal MST — pick by how the graph is represented.

Python

import heapq

def prim(adj, n):
    """adj[u] = list of (neighbor, weight)"""
    visited = [False] * n
    heap = [(0, 0)]   # (cost, node)
    mst_weight = 0
    while heap:
        cost, node = heapq.heappop(heap)
        if visited[node]: continue
        visited[node] = True; mst_weight += cost
        for nb, w in adj[node]:
            if not visited[nb]: heapq.heappush(heap, (w, nb))
    return mst_weight

Java

int prim(List<List<int[]>> adj, int n) {
    boolean[] visited = new boolean[n];
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[]{0, 0});
    int mstWeight = 0;
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int cost = cur[0], node = cur[1];
        if (visited[node]) continue;
        visited[node] = true; mstWeight += cost;
        for (int[] edge : adj.get(node))
            if (!visited[edge[0]]) pq.offer(new int[]{edge[1], edge[0]});
    }
    return mstWeight;
}

C++

int prim(vector<vector<pair<int,int>>>& adj, int n) {
    vector<bool> visited(n, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, 0});
    int mstWeight = 0;
    while (!pq.empty()) {
        auto [cost, node] = pq.top(); pq.pop();
        if (visited[node]) continue;
        visited[node] = true; mstWeight += cost;
        for (auto [nb, w] : adj[node])
            if (!visited[nb]) pq.push({w, nb});
    }
    return mstWeight;
}

Part 8 — Strongly Connected Components (SCC)

Why Do We Need SCC? — A Beginner's Story

Imagine analyzing Twitter follow relationships. An SCC is a group of users where everyone can reach everyone else by following the chain of who follows whom. For example, if Alice follows Bob, Bob follows Charlie, and Charlie follows Alice, they form one SCC — a tight-knit clique.

In software, SCCs appear in:

Compiler analysis: Finding which groups of functions are mutually recursive
2-SAT problems: Constraint satisfaction in competitive programming
Deadlock detection: Groups of processes waiting on each other
Web page ranking: Finding communities of tightly linked pages

Collapse each SCC to a single "super-node" and the resulting graph is always a DAG — this simplification is useful for many advanced algorithms.

Interview reality check: SCC algorithms (Kosaraju's, Tarjan's) are staff-level / competitive programming material. They are rare in standard product-company interviews (Google, Meta, Amazon). Master Parts 1–7 thoroughly first. Read this for awareness.

In a directed graph, a strongly connected component is a maximal group of nodes where every node can reach every other following edge directions.

Kosaraju's Algorithm (2-pass DFS)

Intuition: DFS once to order nodes by finish time, reverse every edge, then DFS again in that finish order — each tree the second pass produces is exactly one SCC. Two passes, easy to remember.

Python

def kosaraju(adj, n):
    visited = [False] * n; stack = []
    def dfs1(node):
        visited[node] = True
        for nb in adj[node]:
            if not visited[nb]: dfs1(nb)
        stack.append(node)
    for i in range(n):
        if not visited[i]: dfs1(i)
    radj = [[] for _ in range(n)]
    for u in range(n):
        for v in adj[u]: radj[v].append(u)
    visited = [False] * n; sccs = []
    def dfs2(node, comp):
        visited[node] = True; comp.append(node)
        for nb in radj[node]:
            if not visited[nb]: dfs2(nb, comp)
    while stack:
        node = stack.pop()
        if not visited[node]:
            comp = []; dfs2(node, comp); sccs.append(comp)
    return sccs

Java

List<List<Integer>> kosaraju(List<List<Integer>> adj, int n) {
    boolean[] visited = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (!visited[i]) dfs1(adj, i, visited, stack);

    List<List<Integer>> radj = new ArrayList<>();
    for (int i = 0; i < n; i++) radj.add(new ArrayList<>());
    for (int u = 0; u < n; u++) for (int v : adj.get(u)) radj.get(v).add(u);

    Arrays.fill(visited, false);
    List<List<Integer>> sccs = new ArrayList<>();
    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (!visited[node]) {
            List<Integer> comp = new ArrayList<>();
            dfs2(radj, node, visited, comp);
            sccs.add(comp);
        }
    }
    return sccs;
}
void dfs1(List<List<Integer>> adj, int u, boolean[] vis, Deque<Integer> stack) {
    vis[u] = true;
    for (int v : adj.get(u)) if (!vis[v]) dfs1(adj, v, vis, stack);
    stack.push(u);
}
void dfs2(List<List<Integer>> radj, int u, boolean[] vis, List<Integer> comp) {
    vis[u] = true; comp.add(u);
    for (int v : radj.get(u)) if (!vis[v]) dfs2(radj, v, vis, comp);
}

C++

void dfs1(vector<vector<int>>& adj, int u, vector<bool>& visited, stack<int>& stk) {
    visited[u] = true;
    for (int v : adj[u]) if (!visited[v]) dfs1(adj, v, visited, stk);
    stk.push(u);
}
void dfs2(vector<vector<int>>& radj, int u, vector<bool>& visited, vector<int>& comp) {
    visited[u] = true; comp.push_back(u);
    for (int v : radj[u]) if (!visited[v]) dfs2(radj, v, visited, comp);
}
vector<vector<int>> kosaraju(vector<vector<int>>& adj, int n) {
    stack<int> stk; vector<bool> visited(n, false);
    for (int i = 0; i < n; i++) if (!visited[i]) dfs1(adj, i, visited, stk);
    vector<vector<int>> radj(n);
    for (int u = 0; u < n; u++) for (int v : adj[u]) radj[v].push_back(u);
    fill(visited.begin(), visited.end(), false);
    vector<vector<int>> sccs;
    while (!stk.empty()) {
        int node = stk.top(); stk.pop();
        if (!visited[node]) {
            vector<int> comp; dfs2(radj, node, visited, comp); sccs.push_back(comp);
        }
    }
    return sccs;
}

Tarjan's Algorithm (single-pass, low-link values)

Intuition: a single DFS that stamps each node with a discovery time and a low-link — the earliest node reachable from its subtree. When a node's low-link equals its own discovery time, it's the root of an SCC, so pop the working stack down to it. One pass instead of Kosaraju's two, same result.

Python

def tarjan(adj, n):
    disc = [-1]*n; low = [0]*n; on_stack = [False]*n
    stack = []; timer = [0]; sccs = []
    def dfs(u):
        disc[u] = low[u] = timer[0]; timer[0] += 1
        stack.append(u); on_stack[u] = True
        for v in adj[u]:
            if disc[v] == -1: dfs(v); low[u] = min(low[u], low[v])
            elif on_stack[v]: low[u] = min(low[u], disc[v])
        if low[u] == disc[u]:
            scc = []
            while True:
                w = stack.pop(); on_stack[w] = False; scc.append(w)
                if w == u: break
            sccs.append(scc)
    for i in range(n):
        if disc[i] == -1: dfs(i)
    return sccs

Java

int timer = 0;
int[] disc, low;
boolean[] onStack;
Deque<Integer> stack;
List<List<Integer>> sccs;

List<List<Integer>> tarjan(List<List<Integer>> adj, int n) {
    disc = new int[n]; Arrays.fill(disc, -1);
    low = new int[n]; onStack = new boolean[n];
    stack = new ArrayDeque<>(); sccs = new ArrayList<>();
    for (int i = 0; i < n; i++) if (disc[i] == -1) tarjanDFS(adj, i);
    return sccs;
}
void tarjanDFS(List<List<Integer>> adj, int u) {
    disc[u] = low[u] = timer++;
    stack.push(u); onStack[u] = true;
    for (int v : adj.get(u)) {
        if (disc[v] == -1) { tarjanDFS(adj, v); low[u] = Math.min(low[u], low[v]); }
        else if (onStack[v]) low[u] = Math.min(low[u], disc[v]);
    }
    if (low[u] == disc[u]) {
        List<Integer> scc = new ArrayList<>();
        while (true) {
            int w = stack.pop(); onStack[w] = false; scc.add(w);
            if (w == u) break;
        }
        sccs.add(scc);
    }
}

C++

int timer_t;
vector<int> disc_t, low_t;
vector<bool> onStack;
stack<int> stk_t;
vector<vector<int>> sccs_t;

void tarjanDFS(vector<vector<int>>& adj, int u) {
    disc_t[u] = low_t[u] = timer_t++;
    stk_t.push(u); onStack[u] = true;
    for (int v : adj[u]) {
        if (disc_t[v] == -1) { tarjanDFS(adj, v); low_t[u] = min(low_t[u], low_t[v]); }
        else if (onStack[v]) low_t[u] = min(low_t[u], disc_t[v]);
    }
    if (low_t[u] == disc_t[u]) {
        vector<int> scc;
        while (true) {
            int w = stk_t.top(); stk_t.pop(); onStack[w] = false; scc.push_back(w);
            if (w == u) break;
        }
        sccs_t.push_back(scc);
    }
}
vector<vector<int>> tarjan(vector<vector<int>>& adj, int n) {
    disc_t.assign(n,-1); low_t.assign(n,0); onStack.assign(n,false);
    timer_t = 0;
    for (int i = 0; i < n; i++) if (disc_t[i] == -1) tarjanDFS(adj, i);
    return sccs_t;
}

Part 9 — Bridges & Articulation Points

Why Do We Need These? — A Beginner's Story

Imagine a computer network. A bridge is a network cable whose removal would split the network into two disconnected parts — it is the single point of failure. An articulation point is a router whose failure would disconnect the network.

Real-world uses:

Network infrastructure: Identifying critical links to protect or duplicate
Road networks: Finding roads whose closure would isolate a community
Biology: Critical proteins in a protein interaction network

The algorithm uses DFS + low-link values — the earliest ancestor reachable from a node's subtree.

A bridge is an edge whose removal disconnects the graph; an articulation point is a node whose removal does. Both find single points of failure — critical links in a network, weak spots in a road or utility grid.

Find all bridges (critical edges)

Intuition: one DFS tracking each node's discovery time and its low-link (the earliest ancestor reachable from its subtree). The edge u→v is a bridge when v's subtree has no back edge climbing above v — written low[v] > disc[u] — which means that single edge is the only way into the subtree.

Python

def find_bridges(adj, n):
    disc = [-1]*n; low = [0]*n; timer = [0]; bridges = []
    def dfs(u, parent):
        disc[u] = low[u] = timer[0]; timer[0] += 1
        for v in adj[u]:
            if disc[v] == -1:
                dfs(v, u); low[u] = min(low[u], low[v])
                if low[v] > disc[u]: bridges.append((u, v))
            elif v != parent:
                low[u] = min(low[u], disc[v])
    for i in range(n):
        if disc[i] == -1: dfs(i, -1)
    return bridges

Java

int timerB; int[] discB, lowB; List<int[]> bridges;
List<int[]> findBridges(List<List<Integer>> adj, int n) {
    discB = new int[n]; Arrays.fill(discB, -1); lowB = new int[n]; bridges = new ArrayList<>();
    for (int i = 0; i < n; i++) if (discB[i] == -1) bridgeDFS(adj, i, -1);
    return bridges;
}
void bridgeDFS(List<List<Integer>> adj, int u, int parent) {
    discB[u] = lowB[u] = timerB++;
    for (int v : adj.get(u)) {
        if (discB[v] == -1) {
            bridgeDFS(adj, v, u); lowB[u] = Math.min(lowB[u], lowB[v]);
            if (lowB[v] > discB[u]) bridges.add(new int[]{u, v});
        } else if (v != parent) lowB[u] = Math.min(lowB[u], discB[v]);
    }
}

C++

int timerB;
vector<int> discB, lowB;
vector<pair<int,int>> bridges;

void bridgeDFS(vector<vector<int>>& adj, int u, int parent) {
    discB[u] = lowB[u] = timerB++;
    for (int v : adj[u]) {
        if (discB[v] == -1) {
            bridgeDFS(adj, v, u);
            lowB[u] = min(lowB[u], lowB[v]);
            if (lowB[v] > discB[u]) bridges.push_back({u, v});
        } else if (v != parent) lowB[u] = min(lowB[u], discB[v]);
    }
}
vector<pair<int,int>> findBridges(vector<vector<int>>& adj, int n) {
    discB.assign(n,-1); lowB.assign(n,0); timerB = 0;
    for (int i = 0; i < n; i++) if (discB[i] == -1) bridgeDFS(adj, i, -1);
    return bridges;
}

Find all articulation points

Intuition: the same DFS + low-link machinery. A node u is an articulation point when some child's subtree can't reach above u (low[child] >= disc[u]) — with one special case for the DFS root, which is a cut vertex only if it has two or more DFS children.

Python

def find_articulation_points(adj, n):
    disc = [-1]*n; low = [0]*n; parent = [-1]*n; timer = [0]; ap = set()
    def dfs(u):
        disc[u] = low[u] = timer[0]; timer[0] += 1; children = 0
        for v in adj[u]:
            if disc[v] == -1:
                children += 1; parent[v] = u; dfs(v)
                low[u] = min(low[u], low[v])
                if parent[u] == -1 and children > 1: ap.add(u)
                if parent[u] != -1 and low[v] >= disc[u]: ap.add(u)
            elif v != parent[u]:
                low[u] = min(low[u], disc[v])
    for i in range(n):
        if disc[i] == -1: dfs(i)
    return ap

Java

int timerAP; int[] discAP, lowAP, parentAP; Set<Integer> ap;
Set<Integer> findAP(List<List<Integer>> adj, int n) {
    discAP = new int[n]; Arrays.fill(discAP,-1); lowAP = new int[n];
    parentAP = new int[n]; Arrays.fill(parentAP,-1); ap = new HashSet<>();
    for (int i = 0; i < n; i++) if (discAP[i] == -1) apDFS(adj, i);
    return ap;
}
void apDFS(List<List<Integer>> adj, int u) {
    discAP[u] = lowAP[u] = timerAP++; int children = 0;
    for (int v : adj.get(u)) {
        if (discAP[v] == -1) {
            children++; parentAP[v] = u; apDFS(adj, v);
            lowAP[u] = Math.min(lowAP[u], lowAP[v]);
            if (parentAP[u] == -1 && children > 1) ap.add(u);
            if (parentAP[u] != -1 && lowAP[v] >= discAP[u]) ap.add(u);
        } else if (v != parentAP[u]) lowAP[u] = Math.min(lowAP[u], discAP[v]);
    }
}

C++

int timerAP;
vector<int> discAP, lowAP, parentAP;
set<int> ap;

void apDFS(vector<vector<int>>& adj, int u) {
    discAP[u] = lowAP[u] = timerAP++; int children = 0;
    for (int v : adj[u]) {
        if (discAP[v] == -1) {
            children++; parentAP[v] = u; apDFS(adj, v);
            lowAP[u] = min(lowAP[u], lowAP[v]);
            if (parentAP[u] == -1 && children > 1) ap.insert(u);
            if (parentAP[u] != -1 && lowAP[v] >= discAP[u]) ap.insert(u);
        } else if (v != parentAP[u]) lowAP[u] = min(lowAP[u], discAP[v]);
    }
}
set<int> findAP(vector<vector<int>>& adj, int n) {
    discAP.assign(n,-1); lowAP.assign(n,0); parentAP.assign(n,-1); timerAP = 0;
    for (int i = 0; i < n; i++) if (discAP[i] == -1) apDFS(adj, i);
    return ap;
}

Part 10 — Bipartite Check & Grid Problems

Why Do We Need Bipartite Graphs? — A Beginner's Story

Imagine Uber: on one side you have Drivers, on the other side you have Riders. A driver only connects to a rider (they don't connect to other drivers). This is a bipartite graph — nodes split into two groups where edges only exist BETWEEN groups, never within a group.

Other examples:

Job assignment: Workers on one side, tasks on the other
Course scheduling: Students on one side, time slots on the other
Conflict detection: If you can 2-color a graph (no two adjacent nodes have the same color), it is bipartite

Quick check: A graph is bipartite if and only if it contains no odd-length cycles. The BFS 2-coloring algorithm below detects this automatically.

A graph is bipartite if its nodes split into two groups with no edge inside a group — equivalently, you can 2-colour it. This models "can these be divided into two teams / sides / shifts?" and underpins matching problems.

Bipartite check (BFS 2-coloring)

Intuition: BFS (or DFS) colouring each node the opposite of its parent. If you ever find an edge linking two same-coloured nodes, no valid 2-colouring exists → not bipartite. (Equivalently: a graph is bipartite iff it has no odd-length cycle.)

Python

def is_bipartite(adj, n):
    color = [-1] * n
    for start in range(n):
        if color[start] != -1: continue
        color[start] = 0
        q = deque([start])
        while q:
            node = q.popleft()
            for nb in adj[node]:
                if color[nb] == -1:
                    color[nb] = 1 - color[node]; q.append(nb)
                elif color[nb] == color[node]:
                    return False
    return True

Java

boolean isBipartite(List<List<Integer>> adj, int n) {
    int[] color = new int[n]; Arrays.fill(color, -1);
    for (int start = 0; start < n; start++) {
        if (color[start] != -1) continue;
        color[start] = 0;
        Queue<Integer> q = new ArrayDeque<>(); q.offer(start);
        while (!q.isEmpty()) {
            int node = q.poll();
            for (int nb : adj.get(node)) {
                if (color[nb] == -1) { color[nb] = 1 - color[node]; q.offer(nb); }
                else if (color[nb] == color[node]) return false;
            }
        }
    }
    return true;
}

C++

bool isBipartite(vector<vector<int>>& adj, int n) {
    vector<int> color(n, -1);
    for (int start = 0; start < n; start++) {
        if (color[start] != -1) continue;
        color[start] = 0;
        queue<int> q; q.push(start);
        while (!q.empty()) {
            int node = q.front(); q.pop();
            for (int nb : adj[node]) {
                if (color[nb] == -1) { color[nb] = 1 - color[node]; q.push(nb); }
                else if (color[nb] == color[node]) return false;
            }
        }
    }
    return true;
}

Count Islands (LeetCode 200)

Python

def count_islands(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0
    def dfs(r, c):
        if r<0 or r>=rows or c<0 or c>=cols or grid[r][c]!='1': return
        grid[r][c] = '0'   # sink visited land
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c); count += 1
    return count

Java

int numIslands(char[][] grid) {
    int rows = grid.length, cols = grid[0].length, count = 0;
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            if (grid[r][c] == '1') { sink(grid, r, c, rows, cols); count++; }
    return count;
}
void sink(char[][] grid, int r, int c, int rows, int cols) {
    if (r<0||r>=rows||c<0||c>=cols||grid[r][c]!='1') return;
    grid[r][c]='0';
    sink(grid,r+1,c,rows,cols); sink(grid,r-1,c,rows,cols);
    sink(grid,r,c+1,rows,cols); sink(grid,r,c-1,rows,cols);
}

C++

void sink(vector<vector<char>>& grid, int r, int c, int rows, int cols) {
    if (r<0||r>=rows||c<0||c>=cols||grid[r][c]!='1') return;
    grid[r][c]='0';
    sink(grid,r+1,c,rows,cols); sink(grid,r-1,c,rows,cols);
    sink(grid,r,c+1,rows,cols); sink(grid,r,c-1,rows,cols);
}
int numIslands(vector<vector<char>>& grid) {
    int rows=grid.size(), cols=grid[0].size(), count=0;
    for (int r=0;r<rows;r++) for (int c=0;c<cols;c++)
        if (grid[r][c]=='1') { sink(grid,r,c,rows,cols); count++; }
    return count;
}

Part 11 — Classic Problems

These tie the techniques together — each is a famous LeetCode problem that's really one of the patterns above wearing a costume.

Rotting Oranges (Multi-source BFS)

The pattern: every rotten orange is a BFS source. Seed them all at minute 0 and let the wavefront spread one minute per BFS level; the answer is the last level reached — pure multi-source BFS from earlier. If any fresh orange is never reached, it can never rot, so return −1.

Python

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    q, fresh = deque(), 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2: q.append((r,c,0))
            elif grid[r][c] == 1: fresh += 1
    time = 0
    for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
        pass
    dirs = [(0,1),(0,-1),(1,0),(-1,0)]
    while q:
        r, c, t = q.popleft()
        for dr, dc in dirs:
            nr, nc = r+dr, c+dc
            if 0<=nr<rows and 0<=nc<cols and grid[nr][nc]==1:
                grid[nr][nc]=2; fresh-=1; time=t+1; q.append((nr,nc,t+1))
    return time if fresh==0 else -1

Java

int orangesRotting(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    Queue<int[]> q = new ArrayDeque<>();
    int fresh = 0;
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 2) q.offer(new int[]{r, c, 0});
            else if (grid[r][c] == 1) fresh++;
        }
    int time = 0;
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int r = cur[0], c = cur[1], t = cur[2];
        for (int[] d : dirs) {
            int nr = r+d[0], nc = c+d[1];
            if (nr>=0&&nr<rows&&nc>=0&&nc<cols&&grid[nr][nc]==1) {
                grid[nr][nc]=2; fresh--; time=t+1; q.offer(new int[]{nr,nc,t+1});
            }
        }
    }
    return fresh == 0 ? time : -1;
}

C++

int orangesRotting(vector<vector<int>>& grid) {
    int rows=grid.size(), cols=grid[0].size(), fresh=0, time=0;
    queue<tuple<int,int,int>> q;
    for (int r=0;r<rows;r++) for (int c=0;c<cols;c++) {
        if (grid[r][c]==2) q.push({r,c,0});
        else if (grid[r][c]==1) fresh++;
    }
    int dirs[][2]={{0,1},{0,-1},{1,0},{-1,0}};
    while (!q.empty()) {
        auto [r,c,t]=q.front(); q.pop();
        for (auto& d:dirs) {
            int nr=r+d[0], nc=c+d[1];
            if (nr>=0&&nr<rows&&nc>=0&&nc<cols&&grid[nr][nc]==1) {
                grid[nr][nc]=2; fresh--; time=t+1; q.push({nr,nc,t+1});
            }
        }
    }
    return fresh==0 ? time : -1;
}

Cheapest Flights Within K Stops (Bellman-Ford)

The pattern: shortest path with a hop limit. Run Bellman-Ford but only k + 1 relaxation rounds — each round lets a path grow by one more edge, so after k+1 rounds you've covered every route using at most k stops. The temp = dist[:] copy each round is essential: it prevents a single round from chaining several flights together (which would exceed the hop budget).

Python

def find_cheapest_price(n, flights, src, dst, k):
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(k + 1):
        temp = dist[:]
        for u, v, price in flights:
            if dist[u] != float('inf') and dist[u] + price < temp[v]:
                temp[v] = dist[u] + price
        dist = temp
    return dist[dst] if dist[dst] != float('inf') else -1

Java

int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    for (int i = 0; i <= k; i++) {
        int[] temp = dist.clone();
        for (int[] f : flights)
            if (dist[f[0]] != Integer.MAX_VALUE && dist[f[0]] + f[2] < temp[f[1]])
                temp[f[1]] = dist[f[0]] + f[2];
        dist = temp;
    }
    return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}

C++

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
    vector<int> dist(n, INT_MAX);
    dist[src] = 0;
    for (int i = 0; i <= k; i++) {
        vector<int> temp = dist;
        for (auto& f : flights)
            if (dist[f[0]] != INT_MAX && dist[f[0]] + f[2] < temp[f[1]])
                temp[f[1]] = dist[f[0]] + f[2];
        dist = temp;
    }
    return dist[dst] == INT_MAX ? -1 : dist[dst];
}

Part 12 — Decision Table

Problem	Algorithm	Why
Shortest path, unweighted	BFS	Level-by-level
Shortest path, weighted ≥ 0	Dijkstra	BFS + min-heap
Shortest path, negative edges	Bellman-Ford	Handles negatives
All-pairs shortest path	Floyd-Warshall	V³, any weights
Topological order	Kahn's BFS	O(V+E), detects cycles
Min spanning tree, sparse	Kruskal	Sort + Union-Find
Min spanning tree, dense	Prim	Heap-based
Strongly connected components	Tarjan	Single-pass
Bridges / articulation points	DFS + low-link	Track back edges
Bipartite check	BFS 2-color	Clean + iterative
Incremental connectivity	Union-Find	α(n) per op

Part 13 — Common Mistakes

Mistake 1: Mark visited on dequeue (BFS)

Mark visited when enqueuing, not when dequeuing. Dequeue-marking lets the same node queue multiple times — corrupts distances.

Mistake 2: Forgetting disconnected graphs

Always loop all nodes and start BFS/DFS from each unvisited one. A single-source traversal misses disconnected components.

Mistake 3: Dijkstra with negative edges

Dijkstra assumes once settled, a node's distance is final. Negative edges can create shorter paths later. Use Bellman-Ford instead.

Mistake 4: Parent check in directed graphs

The if nb != parent check is for undirected graphs only. For directed, use 3-color (white/gray/black). Mixing them silently misses cycles.

Mistake 5: Stale Dijkstra heap entries

After pushing updated distances, old entries stay in the heap. Always check if d > dist[node]: continue (Python) or if (d > dist[node]) continue; when popping.

Think it through

The hardest part of a graph problem is often recognising it's a graph problem at all. Reason through the canonical one — where "prerequisites" quietly means "directed edges" and "can you finish?" means "is there a cycle?". Answer each prompt before revealing.

Think it through: Course ScheduleMedium — LeetCode 2070/5 stages

PROBLEMThere are numCourses courses (0…n−1). prerequisites[i] = [a, b] means you must take b before a. Return whether you can finish every course. Example: 2 courses with [[1,0]] → true; with [[1,0],[0,1]] → false.

1
Reframe as a graph
“What are the nodes, what are the edges, and what does 'can finish all' really ask?”
2
Pick the tool
“Which two standard algorithms decide 'is this directed graph acyclic'?”
unlocks after the stage above
3
Kahn's algorithm, concretely
“What state do I track, and what signals 'no cycle'?”
unlocks after the stage above
4
Code the template
“Build the graph + in-degrees, BFS the zero-in-degree frontier, count.”
unlocks after the stage above
5
Cost & edge check
“Cost, and what exactly does a cycle do to the count?”
unlocks after the stage above

Part 14 — Interview Q&A

Check yourself0/3 answered

1. You need the shortest path in an unweighted graph. Which traversal guarantees it, and why?

2. Why must BFS mark a node visited when it is *enqueued*, not when it is dequeued?

3. Dijkstra fails with negative edge weights because…

Practice — climb the ladder

Three questions before any graph problem: directed or not? weighted or not? what counts as a node? Grids are graphs — neighbors are the 4 cells.

Practice ladder: Graphs — BFS, DFS & Shortest Paths0/23 solved

Climb in order — every rung assumes the one above it. Solve on LeetCode, then tick it here; progress is saved on this device.

Level 1 — Foundations

flood fills, components, basic traversal

Flood FillEasy
DFS on a grid in its smallest form — visit, mark, recurse on 4 neighbors.
Number of IslandsMedium
Connected components — sink each island as you find it; THE graph warm-up.
Find the Town JudgeEasy
Model trust as directed edges; the judge has in-degree n−1 and out-degree 0.
Clone GraphMedium
BFS/DFS with a visited MAP (old → new) — copying while walking.

Level 2 — Core Patterns

multi-source BFS, topological sort, cycle detection

Course ScheduleMedium
Cycle detection / topological sort — prerequisites are directed edges.
Course Schedule IIMedium
Same as above but return the actual topological order via Kahn's BFS.
Rotting OrangesMedium
Multi-source BFS — seed ALL rotten oranges at t=0; each level = one minute.
01 MatrixMedium
Multi-source BFS from every zero simultaneously — distance radiates outward.
Pacific Atlantic Water FlowMedium
Reverse thinking — BFS/DFS FROM both oceans inward, intersect reachable sets.

Level 3 — Weighted Graphs

Dijkstra, Union-Find, BFS on implicit graphs

Network Delay TimeMedium
Classic Dijkstra — single source, non-negative weights, answer is max dist.
Path with Maximum ProbabilityMedium
Max-heap Dijkstra — flip to maximization by negating or using a max-heap.
Number of Connected Components in an Undirected GraphMedium
Union-Find or DFS — count distinct components after merging all edges.
Graph Valid TreeMedium
Tree = connected + no cycle = exactly n−1 edges; use Union-Find or BFS.
Word LadderHard
BFS on an implicit graph where nodes = words and edges = one-letter changes.

Level 4 — Advanced

Bellman-Ford, bridges, Eulerian path, constrained BFS

Cheapest Flights Within K StopsMedium
Bellman-Ford with k+1 relaxation rounds — the temp-copy prevents chaining.
Critical Connections in a NetworkHard
Bridge-finding with DFS + low-link values — edge u→v is a bridge when low[v] > disc[u].
Reconstruct ItineraryHard
Hierholzer's algorithm — Eulerian path on a directed multigraph, post-order DFS.
Swim in Rising WaterHard
Dijkstra where cost = max elevation along path, or binary search + BFS/DFS.
Jump Game IVHard
BFS with value-grouped position map — key is grouping same-value positions.

Level 5 — Master

MST edge analysis, all-pairs, SCC

Find Critical and Pseudo-Critical Edges in MSTHard
Kruskal MST with edge inclusion / forced-exclusion to classify each edge.
Minimum Cost to Connect All PointsMedium
Prim's or Kruskal's MST on a dense graph — Manhattan distance as edge weight.
Shortest Path Visiting All NodesHard
BFS on (node, visited-bitmask) state — classic bitmask DP meets BFS.
Bus RoutesHard
BFS on routes (not stops) — model stops-per-route, level = bus transfers taken.