☕ DSA Java Articles

Topics › Graphs › Learning

Traversal Techniques

Medium TUF ID 529 A2ZSDE

Java source ↗ Edit this article ↗

Problem

There are two ways to explore a graph: breadth-first search (BFS) and depth-first search (DFS). This row of the sheets is the BFS one (the SDE sheet lists it simply as “BFS”); DFS has its own article, DFS.

You are given a graph as an adjacency list adj over vertices 0..V-1 (directed or undirected, it makes no difference to the algorithm) and a start vertex, usually 0. Return the vertices in the order BFS visits them: the start first, then its neighbours in the order they appear in adj[start], then their unvisited neighbours, and so on. Only vertices reachable from the start appear.

Constraints: 1 ≤ V, E ≤ 10^4.

Example 1

edges (undirected): 0-1, 0-2, 0-3, 2-4
adj = [[1,2,3], [0], [0,4], [0], [2]]
answer = [0, 1, 2, 3, 4]      // 0, then its neighbours 1 2 3, then 4 (neighbour of 2)

Example 2

edges (undirected): 0-1, 0-2, 1-3, 2-3, 3-4, 4-5
adj = [[1,2], [0,3], [0,3], [1,2,4], [3,5], [4]]
answer = [0, 1, 2, 3, 4, 5]   // 3 is reachable from both 1 and 2 but is listed once

BFS explores in layers: first everything at distance 0 (the start), then everything at distance 1, then distance 2. That layer order is what makes it the tool for shortest paths in unweighted graphs, and it comes from one data structure: a FIFO queue.

Approach 1: Mark on poll (works, but wasteful)

Intuition. Put the start in a queue. Repeatedly take the front vertex; if it has been processed before, ignore it; otherwise record it and append all of its unprocessed neighbours to the back. Because the queue is first-in-first-out, everything discovered at distance d comes out before anything discovered at distance d + 1.

This version marks a vertex as visited only when it comes out of the queue. It produces the correct order: the first copy of a vertex to leave the queue is the copy that entered first, and that is exactly when a standard BFS would have discovered it. But until it is polled, nothing stops other vertices from enqueueing it again. In example 2, vertex 3 is a neighbour of both 1 and 2, so it is enqueued twice and the second copy is thrown away later.

Algorithm.

  1. Enqueue start.
  2. While the queue is not empty: poll u. If u is visited, continue. Otherwise mark it, append it to the answer, and enqueue every neighbour not yet visited.
static List<Integer> markOnPoll(List<List<Integer>> adj, int start) {
    List<Integer> order = new ArrayList<>();
    boolean[] visited = new boolean[adj.size()];
    Deque<Integer> queue = new ArrayDeque<>();
    queue.add(start);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        if (visited[u]) continue;                     // a stale duplicate: u was already processed
        visited[u] = true;
        order.add(u);
        for (int v : adj.get(u)) {
            if (!visited[v]) queue.add(v);
        }
    }
    return order;
}

Complexity. Time O(V + E): each vertex is processed once and each edge pushes at most one entry. Space O(E): the queue can hold an entry per edge rather than per vertex. In a complete graph on V vertices that is about V^2 / 2 entries; the tests run a complete graph on 60 vertices to show that the answer is still right.

Approach 2: Optimal, mark on push

Intuition. Mark a vertex visited the moment it is discovered, that is, when it is pushed into the queue. Then the !visited[v] check stops every later attempt to enqueue it, so each vertex enters the queue exactly once and no stale entries ever appear. The order is identical to approach 1, and the queue never holds more than V entries.

Algorithm.

  1. Mark start and enqueue it.
  2. While the queue is not empty: poll u and append it to the answer.
  3. For each neighbour v of u in list order: if v is not visited, mark it and enqueue it.
static List<Integer> bfs(List<List<Integer>> adj, int start) {
    List<Integer> order = new ArrayList<>();
    boolean[] visited = new boolean[adj.size()];
    Deque<Integer> queue = new ArrayDeque<>();
    visited[start] = true;
    queue.add(start);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order.add(u);
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                visited[v] = true;                    // mark now so nobody else enqueues v again
                queue.add(v);
            }
        }
    }
    return order;
}

Dry run on example 2:

step polled neighbours scanned newly enqueued queue after order
1 0 1, 2 1, 2 [1, 2] 0
2 1 0, 3 3 [2, 3] 0 1
3 2 0, 3 none (3 already marked) [3] 0 1 2
4 3 1, 2, 4 4 [4] 0 1 2 3
5 4 3, 5 5 [5] 0 1 2 3 4
6 5 4 none [] 0 1 2 3 4 5

Step 3 is where the two approaches differ: approach 1 would have pushed a second copy of 3.

Complexity. Time O(V + E): every vertex is enqueued and polled once, and every adjacency list is scanned once (for an undirected graph the lists total 2E entries). Space O(V) for the visited array and the queue, plus the output.

Why BFS finds shortest paths. The queue always contains vertices from at most two consecutive layers, d followed by d + 1. A vertex is first discovered from a vertex one layer closer to the start, so the layer in which BFS first meets a vertex is its distance in edges. This is the property behind every “minimum number of steps” problem on unweighted graphs and grids.

Approach 3: The same BFS, one level at a time

Intuition. Many problems need to know where one layer ends and the next begins: the distance of each vertex, the minutes in Rotten Oranges, the words per step in Word Ladder. At the start of each round the queue contains exactly the current layer, so read its size once and poll exactly that many vertices. Everything they enqueue belongs to the next layer.

static List<List<Integer>> bfsLevels(List<List<Integer>> adj, int start) {
    List<List<Integer>> levels = new ArrayList<>();
    boolean[] visited = new boolean[adj.size()];
    Deque<Integer> queue = new ArrayDeque<>();
    visited[start] = true;
    queue.add(start);
    while (!queue.isEmpty()) {
        int size = queue.size();                      // exactly the vertices of the current level
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            int u = queue.poll();
            level.add(u);
            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    queue.add(v);
                }
            }
        }
        levels.add(level);
    }
    return levels;
}

For example 1 the layers are [[0], [1, 2, 3], [4]], and concatenating them gives the BFS order. The tests check both, and also check that the layers equal the expected distance groups. Time and space are the same as approach 2.

Disconnected graphs

A BFS from one start only reaches that start’s component. To visit every vertex, wrap the BFS in a loop over all vertices and restart it from each vertex that is still unvisited. This is the same outer loop used to count connected components.

static List<Integer> bfsAll(List<List<Integer>> adj) {
    int n = adj.size();
    List<Integer> order = new ArrayList<>();
    boolean[] visited = new boolean[n];
    Deque<Integer> queue = new ArrayDeque<>();
    for (int s = 0; s < n; s++) {
        if (visited[s]) continue;
        visited[s] = true;
        queue.add(s);
        while (!queue.isEmpty()) {
            int u = queue.poll();
            order.add(u);
            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    queue.add(v);
                }
            }
        }
    }
    return order;
}

For the graph 0-1, 2-3, 3-4, a BFS from 0 returns [0, 1], while bfsAll returns [0, 1, 2, 3, 4]. The total cost is still O(V + E), because the visited array is shared across restarts and nothing is processed twice.

BFS versus DFS

  BFS DFS
container queue (FIFO) stack or recursion (LIFO)
order layer by layer one branch as deep as possible, then backtrack
unweighted shortest paths yes no
typical uses distances, minimum steps, multi-source spreading cycles, components, topological order, backtracking
time / space O(V + E) / O(V) O(V + E) / O(V)

On example 1, BFS gives 0 1 2 3 4, while DFS goes deep into vertex 2 before trying 3 and gives 0 1 2 4 3.

Edge cases and pitfalls