Graphs

Updated Nov 16, 2026 · 6 min read
On this page

    Course prerequisites, friend networks, flight routes, a maze, a grid of islands: whenever things are connected to other things in arbitrary ways, neither a list nor a tree fits. Interviewers love these problems because the hard part is rarely the algorithm. It's seeing that the problem is a graph, choosing how to store it, and not visiting the same node twice.

    How it works

    Nodes and edges

    A graph is a set of nodes (also called vertices) and edges between them. Two questions describe any graph:

    • Directed or undirected? "A follows B" is directed; "A and B are friends" is undirected. Prerequisites are directed: you must take A before B.
    • Weighted or not? Road distances and flight prices are weights. Without weights, every edge counts as one step.

    A tree is a special graph: connected, with no cycles. Graphs can have cycles, so every traversal must remember which nodes it has already visited.

    Storing a graph: the adjacency list

    Each node keeps a list of its neighbours; total memory is proportional to nodes plus edges.
    Each node keeps a list of its neighbours; total memory is proportional to nodes plus edges.

    Most interview problems give you an edge list like [[0, 1], [0, 2], [1, 3]] and you build an adjacency list: for each node, the list of its neighbours. It uses O(V + E) memory (V nodes, E edges), and listing a node's neighbours costs only as much as it has.

    An adjacency matrix (matrix[a][b] = 1 if there's an edge) answers "is there an edge from a to b?" in O(1) but always uses O(V²) memory. Use it only for small, dense graphs.

    Grids are graphs too

    Each cell is a node connected to its up, down, left and right neighbours; you compute them from the coordinates instead of storing edges.
    Each cell is a node connected to its up, down, left and right neighbours; you compute them from the coordinates instead of storing edges.

    A 2D grid is an implicit graph: cell (r, c) connects to (r−1, c), (r+1, c), (r, c−1) and (r, c+1). You never build an adjacency list; you loop over four direction offsets and skip cells outside the grid or blocked by a wall. Islands, flood fill, rotting oranges and shortest paths in a maze are all grid graphs.

    Two ways to explore

    BFS visits all nodes at distance 1, then distance 2; DFS follows one path as far as it can before backing up.
    BFS visits all nodes at distance 1, then distance 2; DFS follows one path as far as it can before backing up.
    • Breadth-first search (BFS) uses a queue and visits nodes in order of distance from the start. In an unweighted graph, the first time BFS reaches a node is along a shortest path.
    • Depth-first search (DFS) uses recursion or a stack and follows one path as deep as possible, then backtracks. It's the natural fit for "explore everything connected to this", cycle detection and topological sorting.

    Both visit each node and edge once: O(V + E).

    Operations and costs

    TaskToolCost
    Visit everything reachableBFS or DFSO(V + E)
    Count connected groupsDFS from every unvisited node, or union-findO(V + E)
    Shortest path, every edge costs 1BFSO(V + E)
    Shortest path, non-negative weightsDijkstra with a min-heapO((V + E) log V)
    Order tasks with dependenciesTopological sortO(V + E)
    Detect a cycleDFS with three colours (directed), or union-find (undirected)O(V + E)

    When to reach for it

    Listen for these clues:

    • "Connected", "reachable", "groups", "islands", "regions": DFS or BFS from each unvisited node, counting how many times you start.
    • "Minimum number of steps", "shortest", "nearest": BFS when steps cost the same; Dijkstra when they have weights.
    • "Prerequisites", "order", "before", "dependencies": a directed graph and a topological sort.
    • "Spread at the same time from several places": multi-source BFS (start with all sources in the queue).
    • Edges arriving one by one, "are these now connected?": union-find.

    Example

    Shortest distance (in edges) from node 0 to every node, with BFS, on the graph in the first picture:

    from collections import deque, defaultdict
    
    def bfs_distances(n, edges, start):
        adj = defaultdict(list)
        for a, b in edges:                 # undirected: add both directions
            adj[a].append(b)
            adj[b].append(a)
        dist = [-1] * n                    # -1 means not visited yet
        dist[start] = 0
        q = deque([start])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if dist[v] == -1:          # mark when you enqueue, not when you dequeue
                    dist[v] = dist[u] + 1
                    q.append(v)
        return dist
    int[] bfsDistances(int n, int[][] edges, int start) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        dist[start] = 0;
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(start);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.offer(v);
                }
            }
        }
        return dist;
    }
    vector<int> bfsDistances(int n, const vector<pair<int, int>>& edges, int start) {
        vector<vector<int>> adj(n);
        for (auto [a, b] : edges) { adj[a].push_back(b); adj[b].push_back(a); }
        vector<int> dist(n, -1);
        dist[start] = 0;
        queue<int> q;
        q.push(start);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }
        return dist;
    }
    func bfsDistances(n int, edges [][2]int, start int) []int {
        adj := make([][]int, n)
        for _, e := range edges {
            adj[e[0]] = append(adj[e[0]], e[1])
            adj[e[1]] = append(adj[e[1]], e[0])
        }
        dist := make([]int, n)
        for i := range dist {
            dist[i] = -1
        }
        dist[start] = 0
        queue := []int{start}
        for len(queue) > 0 {
            u := queue[0]
            queue = queue[1:]
            for _, v := range adj[u] {
                if dist[v] == -1 {
                    dist[v] = dist[u] + 1
                    queue = append(queue, v)
                }
            }
        }
        return dist
    }

    Time: O(V + E). Space: O(V + E) for the adjacency list, O(V) for the queue and distances. For edges [[0,1],[0,2],[1,3],[2,3],[3,4]] the result is [0, 1, 1, 2, 3].

    Counting connected groups uses DFS instead: start a DFS from every node that hasn't been seen yet, and count how many times you start.

    def count_components(n, edges):
        adj = defaultdict(list)
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)
        seen = [False] * n
        def dfs(u):
            seen[u] = True
            for v in adj[u]:
                if not seen[v]:
                    dfs(v)
        count = 0
        for u in range(n):
            if not seen[u]:
                count += 1
                dfs(u)
        return count

    Common mistakes

    • No visited set. Graphs have cycles; without one, BFS and DFS loop forever.
    • Marking visited too late in BFS. Mark a node when you add it to the queue. Marking on removal lets the same node be queued many times.
    • Adding only one direction for an undirected edge.
    • Forgetting isolated nodes. Nodes with no edges never appear in the edge list; loop over range(n), not just the keys of the adjacency map.
    • Using DFS for shortest paths. DFS finds a path, not the shortest. Use BFS (or Dijkstra with weights).
    • Recursion depth. A DFS on a 1,000 × 1,000 grid can recurse a million levels deep; Python's default limit is 1,000. Use an explicit stack or BFS for big grids.
    • Grid bounds. Check 0 <= r < rows and 0 <= c < cols before reading a neighbour.

    Say this in the interview

    • "This is a graph problem: the courses are nodes and each prerequisite is a directed edge."
    • "I'll build an adjacency list, which is O(V + E) memory, and run BFS because every move costs one step, so the first time I reach the target is the shortest path."
    • "I'll mark nodes visited when I enqueue them so nothing is processed twice. Total time is O(V + E)."

    Used in