Graph Traversal Pattern in Java - Interview Preparation Guide

Graph traversal is foundational for connectivity, reachability, and component analysis. The two primary techniques are DFS and BFS.

Graph Representation

List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int[] e : edges) {
    g.get(e[0]).add(e[1]);
    g.get(e[1]).add(e[0]); // undirected
}

DFS Template

What we are doing actually:

Mark the current node as visited as soon as we enter it.
Explore every unvisited neighbor recursively.
Let recursion finish one branch fully before moving to the next.

public void dfs(int u, List<List<Integer>> g, boolean[] vis) {
    vis[u] = true; // Mark on entry to avoid revisiting cycles.
    for (int v : g.get(u)) {
        if (!vis[v]) dfs(v, g, vis);
    }
}

Debug steps:

print u when entering DFS
verify vis[u] is set before recursing to neighbors
test a cyclic graph to confirm nodes are not revisited

BFS Template

What we are doing actually:

Start from the source node.
Mark it visited before enqueueing neighbors.
Process nodes in queue order so exploration happens layer by layer.

public void bfs(int src, List<List<Integer>> g, boolean[] vis) {
    Queue<Integer> q = new ArrayDeque<>();
    q.offer(src);
    vis[src] = true;

    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : g.get(u)) {
            if (!vis[v]) {
                vis[v] = true; // Mark before enqueue to avoid duplicates.
                q.offer(v);
            }
        }
    }
}

Debug steps:

print queue contents after each poll
verify nodes are marked visited before enqueue, not after dequeue
compare DFS order and BFS order on the same small graph

Problem 1: Number of Provinces

Problem description: Count how many connected components exist in the adjacency-matrix graph.

What we are doing actually:

Scan every city.
When we find an unvisited city, it starts a new province.
DFS marks the entire province so it is not counted again.

public int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    boolean[] vis = new boolean[n];
    int count = 0;

    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            count++; // Found a new connected component.
            dfsMatrix(i, isConnected, vis);
        }
    }
    return count;
}

private void dfsMatrix(int u, int[][] g, boolean[] vis) {
    vis[u] = true;
    for (int v = 0; v < g.length; v++) {
        if (g[u][v] == 1 && !vis[v]) dfsMatrix(v, g, vis); // Visit directly connected city.
    }
}

Debug steps:

print which city starts each new province
trace all cities visited from that starting city
verify diagonal g[u][u] values do not inflate the count

Problem 2: Number of Islands

Problem description: Count how many disconnected land regions exist in the grid.

What we are doing actually:

Scan the grid cell by cell.
When we hit land, count one island.
Flood-fill the whole island to mark it visited.

public int numIslands(char[][] grid) {
    int m = grid.length, n = grid[0].length, islands = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                islands++; // New island discovered.
                flood(grid, i, j);
            }
        }
    }
    return islands;
}

private void flood(char[][] g, int r, int c) {
    if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;
    g[r][c] = '0'; // Mark visited so this land is not counted again.
    flood(g, r + 1, c);
    flood(g, r - 1, c);
    flood(g, r, c + 1);
    flood(g, r, c - 1);
}

Debug steps:

print the grid coordinates where each island starts
trace one flood-fill to confirm all connected land turns to water
test isolated single-cell islands and one large island

Dry Run (BFS Traversal)

Graph:

0 -- 1 -- 2
|         |
3 --------4

Start BFS from 0:

queue [0], visit 0
pop 0, push neighbors 1,3
pop 1, push 2
pop 3, push 4 (if not visited)
pop 2, 4 already queued/visited
pop 4, done

Visited order depends on adjacency order, but reachability set is deterministic.

Common Mistakes

Missing visited tracking in cyclic graphs
Stack overflow on deep recursive DFS
Wrong directed vs undirected edge construction
Mutating shared graph state unintentionally

Iterative DFS for Deep Graphs

For very deep inputs, prefer explicit stack to avoid recursion depth issues:

Deque<Integer> st = new ArrayDeque<>();
st.push(src);
while (!st.isEmpty()) {
    int u = st.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (int v : g.get(u)) if (!vis[v]) st.push(v);
}