Graph Interview Problems: BFS, DFS, Connected Components & Cycle Detection

Graph problems scare people because the inputs look different every time: a list of edges, a 2D grid, a dictionary of words, a set of prerequisites, a list of accounts. But underneath, the algorithms are a small toolkit. Once you can translate any input into "vertices and edges" and you have two traversal templates committed to memory, most medium-level graph questions become 15-minute problems.

This guide covers representations, the BFS and DFS templates in three languages, connected components, grid graphs, multi-source BFS, cycle detection for both directed and undirected graphs, bipartite checks, and implicit graphs like Word Ladder. Weighted shortest paths, topological sort and union-find each have their own deep dives, linked where they come up.

How to Represent a Graph in an Interview

The first decision, often made silently, is how to store the graph. Get this right and the rest of the code is short.

Most problems hand you an edge list such as edges = [[0,1],[1,2],[3,4]] and expect you to build the adjacency list yourself:

List<List<Integer>> buildGraph(int n, int[][] edges, boolean directed) {
    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]);
        if (!directed) adj.get(e[1]).add(e[0]);
    }
    return adj;
}

from collections import defaultdict

def build_graph(edges, directed=False):
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        if not directed:
            adj[v].append(u)
    return adj

Use defaultdict(list) in Python when node labels are strings or sparse integers. In Java and C++, a vector<vector<int>> of size n is faster than a hash map when nodes are 0..n-1. Always ask: "Are nodes labelled 0 to n-1? Can there be self-loops or duplicate edges? Is the graph connected?" Those three questions catch most edge cases before you write code.

The BFS Template (and Why It Finds Shortest Paths)

Breadth-first search explores the graph in layers: first the source, then everything one edge away, then everything two edges away. Because a node is first discovered from the earliest possible layer, the layer number at discovery is its shortest distance in edges. That property holds only when every edge has the same weight; for weights you need Dijkstra (see shortest path algorithms).

int[] bfs(List<List<Integer>> adj, int src) {
    int n = adj.size();
    int[] dist = new int[n];
    Arrays.fill(dist, -1);              // -1 doubles as "not visited"
    Deque<Integer> queue = new ArrayDeque<>();
    dist[src] = 0;
    queue.offer(src);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v : adj.get(u)) {
            if (dist[v] == -1) {        // mark on discovery, not on pop
                dist[v] = dist[u] + 1;
                queue.offer(v);
            }
        }
    }
    return dist;
}

vector<int> bfs(const vector<vector<int>>& adj, int src) {
    vector<int> dist(adj.size(), -1);
    queue<int> q;
    dist[src] = 0;
    q.push(src);
    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;
}

from collections import deque

def bfs(adj, src, n):
    dist = [-1] * n
    dist[src] = 0
    q = deque([src])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

Two details matter. First, use a real queue: ArrayDeque in Java, deque in Python. A Python list.pop(0) is O(n) and turns BFS quadratic. Second, when the problem needs explicit levels (for example "minimum minutes" or "level order"), process the queue one layer at a time with an inner loop over len(q), or simply store the distance as above.

def bfs_levels(adj, src):
    seen = {src}
    q = deque([src])
    level = 0
    while q:
        for _ in range(len(q)):         # exactly the nodes of this level
            u = q.popleft()
            # process u at distance `level`
            for v in adj[u]:
                if v not in seen:
                    seen.add(v)
                    q.append(v)
        level += 1

The DFS Template: Recursive and Iterative

Depth-first search goes as deep as possible along one path before backtracking. It does not give shortest paths, but it naturally exposes structure: which nodes are in the same component, whether there is a back edge (cycle), and the order in which nodes finish (topological sort).

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

def dfs_iterative(adj, src, n):
    visited = [False] * n
    stack = [src]
    order = []
    while stack:
        u = stack.pop()
        if visited[u]:
            continue                    # may be pushed more than once
        visited[u] = True
        order.append(u)
        for v in reversed(adj[u]):      # reversed keeps the recursive visiting order
            if not visited[v]:
                stack.append(v)
    return order

Note the subtle difference: in iterative DFS we mark on pop, and a node can sit on the stack more than once. That is fine for reachability, and the stack holds at most O(E) entries. If you need pre/post-order timing (for cycle detection or topological order), recursion is far easier to get right, so in Python raise the limit with sys.setrecursionlimit(10**6) and say why.

Connected Components: Counting and Labelling

A connected component is a maximal set of vertices where each pair is linked by a path. To count components, loop over every vertex; each time you meet an unvisited one, start a traversal from it and increment the count. Every vertex and edge is touched once overall, so it is still O(V + E).

int countComponents(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    vector<bool> seen(n, false);
    int components = 0;
    for (int s = 0; s < n; s++) {
        if (seen[s]) continue;
        components++;
        stack<int> st;
        st.push(s);
        seen[s] = true;
        while (!st.empty()) {
            int u = st.top(); st.pop();
            for (int v : adj[u]) {
                if (!seen[v]) { seen[v] = true; st.push(v); }
            }
        }
    }
    return components;
}

Variants you will meet: Number of Provinces (547) gives an adjacency matrix instead of an edge list, so neighbours come from scanning a row and the complexity becomes O(n²). Graph Valid Tree (261) asks whether the graph is one component with no cycle; the fast check is "exactly n−1 edges and connected". When edges arrive over time and you need component counts after each one, switch to union-find, which answers in near-constant time per edge.

Grid Graph Problems: Islands, Flood Fill and Boundaries

An R × C grid is a graph with R·C vertices, where each cell connects to its up, down, left and right neighbours (sometimes 8 directions). You never build an adjacency list; you compute neighbours with a direction array.

def num_islands(grid):
    if not grid:
        return 0
    R, C = len(grid), len(grid[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    count = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] != "1":
                continue
            count += 1
            grid[r][c] = "0"            # sink as we go: grid doubles as visited
            stack = [(r, c)]
            while stack:
                x, y = stack.pop()
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < R and 0 <= ny < C and grid[nx][ny] == "1":
                        grid[nx][ny] = "0"
                        stack.append((nx, ny))
    return count

Dry run on this 4 × 5 grid:

Scanning row by row: (0,0) is land, count = 1, the flood fill sinks (0,0), (1,0), (0,1), (1,1). Next land found during the scan is (2,2): count = 2, sinks just itself (diagonals do not count). Next is (3,3): count = 3, sinks (3,3) and (3,4). Answer 3. Time O(R·C), since each cell is sunk once and checked from at most 4 neighbours. Space O(R·C) worst case for the stack. The full write-up with BFS and union-find versions is in LeetCode 200 explained.

Mutating the input is a design choice; say it out loud. If the interviewer does not want the grid modified, use a separate visited boolean grid, or restore the cells afterwards.

Boundary-first DFS: Surrounded Regions and Pacific Atlantic

Some grid questions are easier backwards. In Surrounded Regions (130), an 'O' survives only if it connects to the border. Instead of checking every region, start a DFS from every border 'O' and mark those cells safe; then flip every unmarked 'O' to 'X'. In Pacific Atlantic Water Flow (417), run one traversal inward from the Pacific edges (moving only to cells of equal or greater height) and one from the Atlantic edges; the answer is the intersection. Both are O(R·C) instead of O((R·C)²) for the "start from every cell" approach.

Multi-Source BFS: Rotting Oranges, 01 Matrix, Walls and Gates

When the question asks for each cell's distance to the nearest of many sources, do not run BFS from each source. Put all sources in the queue at distance 0 and run a single BFS. It behaves as if a virtual super-source were connected to every real source by a zero-length edge.

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

The loop condition fresh > 0 avoids counting an extra minute after the last orange rots. If any fresh orange is unreachable, fresh stays positive and we return −1. Time O(R·C). Step-by-step grids are in LeetCode 994 explained.

Same skeleton, different seeds:

• 01 Matrix (542): seed all 0-cells, BFS outward to fill distances for 1-cells.
• Walls and Gates (286): seed all gates, fill empty rooms with distance to the nearest gate.
• As Far from Land as Possible (1162): seed all land, the answer is the largest distance reached in water.
• Shortest Bridge (934): DFS to find and mark the first island, then multi-source BFS from all its cells until you hit the second island.

Cycle Detection in Undirected and Directed Graphs

This is the topic where candidates most often apply the wrong technique, because the undirected and directed versions look similar but are not interchangeable.

Undirected graphs: the parent check

In an undirected graph, edge (u, v) appears in both lists, so when DFS goes from u to v, v immediately sees u as a visited neighbour. That is not a cycle; it is the same edge. So track the parent and ignore it. Any other visited neighbour means a cycle.

def has_cycle_undirected(n, adj):
    visited = [False] * n
    for s in range(n):
        if visited[s]:
            continue
        visited[s] = True
        stack = [(s, -1)]
        while stack:
            u, parent = stack.pop()
            for v in adj[u]:
                if not visited[v]:
                    visited[v] = True
                    stack.append((v, u))
                elif v != parent:
                    return True
    return False

One caveat: with parallel edges (two edges between the same u and v), the parent check misses the 2-cycle. If the problem allows multi-edges, track the edge index instead of the parent vertex, or use union-find: process each edge, and if both endpoints already share a root, that edge closes a cycle. That is exactly Redundant Connection (684).

Directed graphs: three colours

In a directed graph, reaching a visited node is not enough. Consider edges A→B, A→C, C→B. DFS visits A, B (finishes), then C, which sees B already visited. There is no cycle; B was in a different, finished branch. A cycle exists only if we reach a node that is still on the current recursion stack (a back edge). So each node has three states:

• WHITE (0): not visited yet.
• GRAY (1): visited, still on the recursion stack.
• BLACK (2): fully explored, all descendants done.

boolean hasCycleDirected(List<List<Integer>> adj) {
    int n = adj.size();
    int[] color = new int[n];
    for (int s = 0; s < n; s++) {
        if (color[s] == 0 && dfsCycle(adj, s, color)) return true;
    }
    return false;
}

private boolean dfsCycle(List<List<Integer>> adj, int u, int[] color) {
    color[u] = 1;                                   // GRAY: on the stack
    for (int v : adj.get(u)) {
        if (color[v] == 1) return true;             // back edge
        if (color[v] == 0 && dfsCycle(adj, v, color)) return true;
    }
    color[u] = 2;                                   // BLACK: done
    return false;
}

The BFS alternative is Kahn's algorithm: repeatedly remove nodes with in-degree 0. If some nodes never reach in-degree 0, they lie on or behind a cycle. That is the standard solution to Course Schedule (207), and both methods are covered in depth in the topological sort guide.

Find Eventual Safe States (802) is a nice twist on the same colouring: a node is safe if it is BLACK and none of its descendants led into a GRAY node. With the three-colour DFS above, every node that finishes as BLACK without detecting a cycle is safe.

Bipartite Graph Check: Two-Colouring with BFS

A graph is bipartite if its vertices can be split into two groups such that every edge goes between the groups. Equivalently, you can colour it with two colours so no edge joins same-coloured vertices, and equivalently, it has no odd-length cycle. Interview disguises: "split people into two teams where no two people who dislike each other share a team" (Possible Bipartition, 886), or Is Graph Bipartite? (785) directly.

bool isBipartite(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> color(n, -1);
    for (int s = 0; s < n; s++) {
        if (color[s] != -1) continue;       // already coloured in an earlier component
        queue<int> q;
        q.push(s);
        color[s] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : graph[u]) {
                if (color[v] == -1) {
                    color[v] = 1 - color[u];
                    q.push(v);
                } else if (color[v] == color[u]) {
                    return false;           // same colour across an edge
                }
            }
        }
    }
    return true;
}

Dry run on the square 0–1–2–3–0: colour 0 → 0. Neighbours 1 and 3 → 1. From 1, neighbour 2 → 0. From 3, neighbour 2 is already 0, which differs from 3's colour 1: fine. Bipartite. Add the diagonal edge 0–2: when processing 0, neighbour 2 gets colour 1; later from 1 (colour 1) we see 2 (colour 1): conflict, not bipartite. The triangle 0–1–2 is the odd cycle.

The outer loop over all start nodes is the part people forget. LeetCode 785 includes disconnected graphs precisely to catch it.

Implicit Graphs: Word Ladder, Open the Lock, Clone Graph

The hardest step in many graph problems is noticing it is a graph at all. If you have states and moves between states, and the question asks for the minimum number of moves, it is BFS on an implicit graph.

Word Ladder (LeetCode 127)

States are words; there is an edge between two words differing in exactly one letter. Comparing every pair is O(N²·L). Instead, generate neighbours by changing each position to each of 26 letters and checking membership in a hash set: O(N·L·26) neighbour checks, each costing O(L) to hash, so O(N·L²·26) overall.

from collections import deque
from string import ascii_lowercase

def ladder_length(begin, end, word_list):
    words = set(word_list)
    if end not in words:
        return 0
    q = deque([(begin, 1)])
    words.discard(begin)
    while q:
        word, steps = q.popleft()
        if word == end:
            return steps
        for i in range(len(word)):
            for ch in ascii_lowercase:
                nxt = word[:i] + ch + word[i + 1:]
                if nxt in words:
                    words.remove(nxt)       # removing from the set = marking visited
                    q.append((nxt, steps + 1))
    return 0

The standard follow-up is bidirectional BFS: expand from both ends, always the smaller frontier, and stop when they meet. With branching factor b and distance d, it explores roughly 2·b^d/2 states instead of b^d.

Open the Lock (752) and other state spaces

A 4-digit lock has 10⁴ states; each state has 8 neighbours (each wheel ±1). Dead-ends are just pre-visited nodes. Sliding Puzzle (773) encodes the board as a string; Minimum Genetic Mutation (433) is Word Ladder with a 4-letter alphabet. Same BFS every time.

Clone Graph (133)

Traverse the original graph with BFS or DFS while keeping a hash map from original node to its copy. When you visit a neighbour, create its copy if it is not in the map (and enqueue it), then append the copy to the current copy's neighbour list. The map doubles as the visited set. O(V + E).

BFS vs DFS: A Decision Table

For memory: BFS holds up to a whole frontier, which in a wide graph can be O(V). DFS holds the current path, which in a long chain can also be O(V). Neither wins universally; the shape of the graph decides.

What Interviewers Look for in Graph Rounds

Graph questions are popular in Amazon, Google, Microsoft, Uber and Flipkart loops because they test modelling as much as coding. Here is what a strong performance looks like.

1. Name the graph. "Vertices are cells, edges connect 4-directional neighbours with value 1." Saying this before coding shows you understand the problem's structure.
2. Pick the traversal with a reason. "We need minimum minutes, so BFS by levels." Not "I'll do DFS" followed by a wrong answer for shortest path.
3. State complexity in terms of the input. "O(R·C) time and space" for grids, "O(V + E)" for edge lists. For Word Ladder, include word length.
4. Handle disconnected graphs. Wrap the traversal in a loop over all vertices whenever the question is about the whole graph.
5. Discuss mutation. Ask whether you may modify the grid. Interviewers at product companies notice when you ask.
6. Know the next step. If edges are added dynamically, mention union-find. If weights appear, mention Dijkstra. If the graph is huge, mention bidirectional BFS.

If you freeze on unfamiliar graph problems, the general framework in how to approach a DSA problem in an interview helps: list inputs, identify states and transitions, then match against the decision table above.

Common Graph Bugs That Cost Offers

• Bounds checks in the wrong order. grid[nr][nc] == 1 && nr >= 0 throws before the bounds check runs. Always check bounds first.
• Using the undirected parent rule on a directed graph (or vice versa). Re-read whether edges are directed.
• Forgetting isolated vertices. Building the adjacency list only from edges misses nodes with no edges; size the list by n.
• Off-by-one in level counting in rotting-oranges-style problems: count a level only if something actually changed, or guard with a remaining-count variable.
• Using a list as a queue in Python. pop(0) is O(n). Use collections.deque.
• Recursion depth on large grids in Python, discussed above.
• Visited as a list of tuples. Membership in a list is O(n). Use a set or a boolean grid.

Graph Practice List: 18 Problems by Sub-Pattern

After these, move on to weighted shortest paths, topological sort and union-find; together with this post they cover essentially every graph question asked in Indian product-company interviews. For a week-by-week order, the DSA roadmap places graphs after trees and before dynamic programming.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.