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 graph is a set of nodes (vertices, V) connected by edges (E). This simple idea captures almost every relationship that matters in computing: social networks, maps, dependency graphs, the internet, compilers, and scheduling systems.

Part 1 — Fundamentals & Representation

Vocabulary

Term	Meaning
Directed / Undirected	Edges have direction (A→B) or go both ways (A↔B)
Weighted	Each edge has a cost/distance
Degree	Number of edges touching a node
Path	A sequence of nodes connected by edges
Cycle	A path that starts and ends at the same node
DAG	Directed Acyclic Graph — directed, no cycles
Connected	Every node reachable from every other (undirected)
Tree	Connected, undirected, no cycles — exactly V-1 edges

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)

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

BFS explores nodes level by level using a queue. The first time you reach a node = shortest path (fewest edges).

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

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

When distances from multiple starting points simultaneously (nearest warehouse, nearest exit):

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

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)

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 dives as deep as possible before backtracking. Natural fit for: connectivity, all paths, cycle detection, topological order, SCCs, bridges.

DFS recursive

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)

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

Cycle in an undirected graph

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 (3-colour DFS)

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)

Linear ordering where every edge u→v has u before v. Only exists if graph is a DAG.

Kahn's Algorithm (BFS-based — preferred)

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>{};
}

Course Schedule (LeetCode 207)

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

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)

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)

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)

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)

Kruskal's Algorithm (sort edges, use 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)

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)

Kosaraju's Algorithm (2-pass DFS)

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)

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

Find all bridges (critical edges)

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

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

Bipartite check (BFS 2-coloring)

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

Rotting Oranges (Multi-source BFS)

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)

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.

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 Ladder

Level 1 — Foundations

Number of Islands (LeetCode 200) — DFS/BFS on grid; do both
Flood Fill (LeetCode 733) — DFS with color matching
Find the Town Judge (LeetCode 997) — in-degree/out-degree
Clone Graph (LeetCode 133) — BFS + hash map

Level 2 — Core Patterns

Course Schedule (LeetCode 207) — topological sort / cycle detection
Course Schedule II (LeetCode 210) — return the actual order
Rotting Oranges (LeetCode 994) — multi-source BFS
01 Matrix (LeetCode 542) — multi-source BFS from all zeros
Pacific Atlantic Water Flow (LeetCode 417) — multi-source DFS from both coasts

Level 3 — Weighted Graphs

Network Delay Time (LeetCode 743) — classic Dijkstra
Path with Maximum Probability (LeetCode 1514) — max-heap Dijkstra
Number of Connected Components (LeetCode 323) — Union-Find
Graph Valid Tree (LeetCode 261) — n-1 edges + no cycle
Word Ladder (LeetCode 127) — BFS on implicit word graph

Level 4 — Advanced

Cheapest Flights Within K Stops (LeetCode 787) — Bellman-Ford with constraint
Critical Connections (LeetCode 1192) — bridges with low-link
Reconstruct Itinerary (LeetCode 332) — Eulerian path on directed graph
Swim in Rising Water (LeetCode 778) — Dijkstra or binary search + BFS
Jump Game IV (LeetCode 1345) — BFS with value-grouped positions

Level 5 — Master

Find Critical and Pseudo-Critical Edges (LeetCode 1489) — Kruskal edge inclusion/exclusion
Implement Kosaraju's + Tarjan's from memory
Floyd-Warshall + transitive closure
Bellman-Ford arbitrage detection on currency graphs
A* search on a grid with heuristics

Next: Union-Find — the data structure for incremental connectivity, and the backbone of Kruskal's MST.

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 & DFS0/9 solved

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

Warm-up

flood the grid

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.

Core

BFS for distance, DFS for structure, topo for order

Rotting OrangesMedium
Multi-source BFS — start the queue with EVERY rotten orange; level = minute.
01 MatrixMedium
Multi-source BFS again, from the zeros — distance fields radiate outward.
Clone GraphMedium
Traversal with a visited MAP (old → new) — copying while walking.
Course ScheduleMedium
Cycle detection / topological sort — prerequisites are a directed graph.
Pacific Atlantic Water FlowMedium
Reverse thinking — flow FROM the oceans inward, intersect the reachable sets.

Stretch

BFS under constraints

Shortest Path in Binary MatrixMedium
BFS = shortest path in unweighted graphs — 8 directions, visited-on-enqueue.
Word LadderHard
Words as nodes, one-letter edits as edges — modeling IS the problem.