Graphs

Dropping the hierarchy

A tree has a root, and every node has exactly one parent. A graph drops both rules. Any node may connect to any other, connections can form loops, and there is no top.

That freedom makes graphs the most general structure in this module. Trees and linked lists are both special cases of a graph.

The pieces have standard names:

• Node (or vertex) — a thing
• Edge — a connection between two things

Recognising one

The word “graph” almost never appears in a problem. What appears is:

• Rooms connected by doors
• Cities joined by roads
• Tasks where one must finish before another
• Grid cells you can walk between
• Web pages linking to each other

All graphs. If the problem describes things and connections between them, that is what you have.

Storing a graph

The usual choice is an adjacency list: for each node, the list of nodes it connects to.

import java.util.*;

int n = 5;                                   // nodes numbered 0..4
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
    adj.add(new ArrayList<>());
}

// add an undirected edge between u and v
void addEdge(List<List<Integer>> adj, int u, int v) {
    adj.get(u).add(v);
    adj.get(v).add(u);        // omit this line for a directed graph
}

When nodes are named rather than numbered, a map works:

Map<String, List<String>> adj = new HashMap<>();

void addEdge(Map<String, List<String>> adj, String a, String b) {
    adj.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
    adj.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
}

computeIfAbsent creates the list on first use, so you avoid a null check on every insert.

Depth-first search

Go as deep as possible along one path before backing up. Naturally recursive.

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);
        }
    }
}

The visited array is not optional. Unlike a tree, a graph can contain loops, so without it the traversal follows a cycle forever. Mark the node at the start of the call, before recursing — marking it afterwards still loops.

Breadth-first search

Explore all immediate neighbours first, then their neighbours, spreading outward in rings. Uses a queue.

static int[] bfs(int start, List<List<Integer>> adj, int n) {
    int[] distance = new int[n];
    Arrays.fill(distance, -1);          // -1 means not reached

    Queue<Integer> queue = new ArrayDeque<>();
    distance[start] = 0;
    queue.offer(start);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        for (int neighbour : adj.get(node)) {
            if (distance[neighbour] == -1) {
                distance[neighbour] = distance[node] + 1;
                queue.offer(neighbour);
            }
        }
    }
    return distance;
}

Here distance doubles as the visited marker — -1 means unreached. Setting it when you offer the node, not when you poll it, is what stops the same node being queued twice.

Counting connected components

A common question: how many separate groups are there? Start a traversal from every node not yet reached; each fresh start is one new group.

boolean[] visited = new boolean[n];
int groups = 0;

for (int i = 0; i < n; i++) {
    if (!visited[i]) {
        groups++;
        dfs(i, adj, visited);
    }
}
System.out.println(groups + " separate groups");

The outer loop matters. Starting only from node 0 finds one group and misses every disconnected part of the graph.

Grids are graphs

A grid problem is a graph problem where cells are nodes and adjacent cells are connected. You do not build an adjacency list — the neighbours are computed from the coordinates.

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

static void explore(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;

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

The bounds checks must come before reading grid[nr][nc]. Java stops evaluating || at the first true condition, so an out-of-range index is never used. Reordering these throws ArrayIndexOutOfBoundsException.

The offset arrays give the four orthogonal neighbours. For diagonal movement too, use all eight combinations of -1, 0, and 1 except (0, 0).

Related

Going further