Graphs

Reach for it when

• Grid of cells (islands, rotting oranges)
• Dependencies or prerequisites (topological sort)
• Connectivity, components, cycle detection

Core idea

Build an adjacency list, then traverse with a visited set. BFS explores in layers and gives shortest paths in unweighted graphs; DFS is simpler for components and cycle detection. Topological sort (Kahn's algorithm) repeatedly removes nodes with in-degree zero; if some remain, there is a cycle. Union-Find answers 'are these connected?' incrementally.

Template · O(V + E) time and space

from collections import deque

def bfs(start, neighbors):
    dist = {start: 0}
    q = deque([start])
    while q:
        node = q.popleft()
        for nxt in neighbors(node):
            if nxt not in dist:          # mark when enqueued
                dist[nxt] = dist[node] + 1
                q.append(nxt)
    return dist

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

Common pitfalls

• Marking visited on dequeue instead of enqueue (duplicates in the queue)
• Multi-source BFS: enqueue all sources at distance 0 first
• Undirected edges must be added in both directions

Practice · 0 / 14 done

• Amount of Time for Binary Tree to Be InfectedMedium
• Clone GraphMedium
• Course ScheduleMedium
• Course Schedule IIMedium
• Graph Valid TreeMedium
• Max Area of IslandMedium
• Number of Connected Components In An Undirected GraphMedium
• Number of IslandsMedium
• Pacific Atlantic Water FlowMedium
• Redundant ConnectionMedium
• Rotting OrangesMedium
• Surrounded RegionsMedium
• Walls And GatesMedium
• Word LadderHard