BFS & DFS

With a graph stored as an adjacency list, the next question is: how do you actually visit every node? The two fundamental approaches are Breadth-First Search (BFS), which explores level by level outward from a start node, and Depth-First Search (DFS), which plunges as deep as possible down one path before backtracking. Both visit every reachable vertex and edge exactly once, just in a different order — and that order matters a lot depending on the problem.

Example Graph

An unweighted, undirected graph with 6 vertices, used for both traversals below:

      0
     / \
    1   2
    |   |
    3   4
     \ /
      5

Edges: 0-1, 0-2, 1-3, 2-4, 3-5, 4-5. We'll start both traversals at vertex 0.

// Adjacency list for the graph above
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < 6; i++) adj.add(new ArrayList<>());

void addEdge(int u, int v) {
    adj.get(u).add(v);
    adj.get(v).add(u);
}

addEdge(0, 1); addEdge(0, 2);
addEdge(1, 3); addEdge(2, 4);
addEdge(3, 5); addEdge(4, 5);

Breadth-First Search (BFS)

BFS uses a queue. It visits the start node, then all of its direct neighbors, then all of their unvisited neighbors, and so on — expanding outward in complete "rings" one level at a time. A visited set stops it from revisiting nodes or looping forever on a cycle.

List<Integer> bfs(List<List<Integer>> adj, int start) {
    List<Integer> order = new ArrayList<>();
    boolean[] visited = new boolean[adj.size()];
    Queue<Integer> queue = new LinkedList<>();

    queue.add(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int node = queue.poll();
        order.add(node);

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;  // mark on enqueue, not on dequeue
                queue.add(neighbor);
            }
        }
    }
    return order;
}

// bfs(adj, 0) on the example graph: [0, 1, 2, 3, 4, 5]
// Level 0: {0} -> Level 1: {1, 2} -> Level 2: {3, 4} -> Level 3: {5}

Time complexity: O(V + E) — every vertex is enqueued once and every edge is examined once (twice for an undirected graph, still a constant factor). Space complexity: O(V) for the visited array and the queue, which can hold up to one full level of the graph at once.

Depth-First Search (DFS)

DFS commits to one path and follows it as far as it can before backtracking, using either explicit recursion (which uses the call stack) or an explicit Stack. It's less "fair" than BFS about exploring breadth-wise, but it's the natural fit for problems about paths, cycles, and structure rather than distance.

List<Integer> dfs(List<List<Integer>> adj, int start) {
    List<Integer> order = new ArrayList<>();
    boolean[] visited = new boolean[adj.size()];
    dfsHelper(adj, start, visited, order);
    return order;
}

void dfsHelper(List<List<Integer>> adj, int node, boolean[] visited, List<Integer> order) {
    visited[node] = true;
    order.add(node);

    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            dfsHelper(adj, neighbor, visited, order);  // recurse depth-first before trying siblings
        }
    }
}

// dfs(adj, 0) on the example graph: [0, 1, 3, 5, 4, 2]
// From 0 -> 1 (first neighbor) -> 3 (its first neighbor) -> 5 -> 4 (5's other neighbor)
// -> backtrack all the way to 0 -> try 0's other neighbor, 2 (already-visited nodes skipped)

Time complexity: O(V + E) — same reasoning as BFS, every vertex and edge is visited exactly once. Space complexity: O(V) — the visited array plus the recursion call stack, which in the worst case (a long path) holds all V frames at once.

BFS vs DFS: When to Choose Which