Depth-First Search

Going deep first

Depth-first search explores by committing to one direction and following it until it dead-ends, then backing up and trying the next option.

On a tree this is exactly pre-order traversal. On a graph one thing changes: a graph can contain cycles, so you must remember where you have been.

static void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
    visited[node] = true;
    System.out.println("visiting " + node);

    for (int neighbour : adj.get(node)) {
        if (!visited[neighbour]) {
            dfs(neighbour, adj, visited);
        }
    }
}

visited[node] = true;      // first line of the method
for (...) { ... }

Counting connected components

The classic use. Start a search from every node not yet reached; each fresh start is one separate group.

static int countComponents(List<List<Integer>> adj, int n) {
    boolean[] visited = new boolean[n];
    int components = 0;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            components++;
            dfs(i, adj, visited);
        }
    }
    return components;
}

The outer loop matters. Searching only from node 0 finds one group and silently misses every disconnected part.

Grid flood fill

A grid is a graph where cells are nodes and adjacent cells are edges. Counting regions of connected cells is the same algorithm:

static final int[] DR = {-1, 1, 0, 0};
static final int[] DC = {0, 0, -1, 1};

static void fill(char[][] grid, boolean[][] seen, int r, int c) {
    seen[r][c] = true;

    for (int d = 0; d < 4; d++) {
        int nr = r + DR[d];
        int nc = c + DC[d];

        if (nr < 0 || nr >= grid.length) continue;
        if (nc < 0 || nc >= grid[0].length) continue;
        if (seen[nr][nc] || grid[nr][nc] == '#') continue;

        fill(grid, seen, nr, nc);
    }
}

The bounds checks must come before reading grid[nr][nc]. Java stops evaluating at the first continue, so an out-of-range index is never used. Reorder them and you get ArrayIndexOutOfBoundsException.

Counting regions then follows the same shape as components:

int regions = 0;
for (int r = 0; r < grid.length; r++) {
    for (int c = 0; c < grid[0].length; c++) {
        if (grid[r][c] == '.' && !seen[r][c]) {
            regions++;
            fill(grid, seen, r, c);
        }
    }
}

Detecting a cycle

In an undirected graph, a cycle exists if you reach an already-visited node that is not the one you came from:

static boolean hasCycle(int node, int parent,
                        List<List<Integer>> adj, boolean[] visited) {
    visited[node] = true;

    for (int neighbour : adj.get(node)) {
        if (!visited[neighbour]) {
            if (hasCycle(neighbour, node, adj, visited)) return true;
        } else if (neighbour != parent) {
            return true;                  // reached a visited node another way
        }
    }
    return false;
}

Passing the parent is what prevents a false positive — every edge you walk down is immediately walkable back up, and that is not a cycle.

For a directed graph the parent trick does not work. You need three states instead of a boolean: unvisited, currently on the stack, and finished. A cycle is an edge back to a node still on the stack.

static final int UNVISITED = 0, IN_PROGRESS = 1, DONE = 2;

static boolean hasCycleDirected(int node, List<List<Integer>> adj, int[] state) {
    state[node] = IN_PROGRESS;

    for (int next : adj.get(node)) {
        if (state[next] == IN_PROGRESS) return true;      // back edge
        if (state[next] == UNVISITED && hasCycleDirected(next, adj, state)) {
            return true;
        }
    }
    state[node] = DONE;
    return false;
}

A plain boolean[] cannot distinguish “on the current path” from “finished elsewhere”, and would report cycles that do not exist.

Iterative DFS

Recursion depth scales with the graph, so a large graph can overflow the stack. An explicit stack removes the limit:

static void dfsIterative(int start, List<List<Integer>> adj, boolean[] visited) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);

    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (visited[node]) continue;      // may have been queued twice
        visited[node] = true;

        for (int neighbour : adj.get(node)) {
            if (!visited[neighbour]) {
                stack.push(neighbour);
            }
        }
    }
}

The if (visited[node]) continue; after popping is needed here. Unlike the recursive version, a node can be pushed several times before it is first popped, so you check on the way out rather than only on the way in.

DFS or BFS

The shortest-path row is the one that catches people. DFS will happily return a long winding route when a direct one exists. If the question involves “fewest steps”, use breadth-first search.

Next

Related