Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

BFS and DFS in Java: A Visual Guide

Learn BFS and DFS with static graph, queue and call-stack traces, tested Java, shortest paths, grids and 12 practical question patterns.

BasicsGraphsPattern: recursion

Imagine a group of rooms connected by doors. You are standing in room A and want to explore the rooms you can reach.

You can explore all rooms one door away before moving farther away. Or you can follow one route as far as it goes, return, and try another route.

Those two choices are Breadth-First Search (BFS) and Depth-First Search (DFS). Their names sound complicated, but their basic difference is simple: which room should we explore next?

This guide starts from zero. We will use the same small graph, watch real queue and stack operations, write Java, and learn how to recognize the idea inside a question that never says “use BFS” or “use DFS.”

You need arrays, loops, and basic Java methods. If recursion is new, keep the beginner’s recursion guide nearby.

For roots, leaves, tree shapes, and the differences between inorder, preorder and postorder, start with Trees and Traversals in Java. This guide then extends those ideas to general graphs.

1. Understand the graph before the algorithm

A node, also called a vertex, represents something: a room, person, computer, cell, or state. An edge represents a connection or allowed move.

Consider this graph:

Worked example · read from top to bottom
             A
           /   \
          B     C
         / \   / \
        D   E F   G

The nodes are A through G. An edge A-B means we can move between A and B.

This particular graph is also a tree: it is connected and has no cycle. We use it first because the order is easy to see. BFS and DFS also work on graphs that have cycles or disconnected parts.

A few words you will meet often

Word Simple meaning
Neighbor A node directly connected to the current node
Path A sequence of allowed moves between nodes
Cycle A route that comes back to where it started
Connected component A group of mutually reachable nodes in an undirected graph
Directed edge A one-way move, such as A → B
Undirected edge A two-way connection, such as A-B
Unweighted graph Every move counts as one step
Weighted graph Edges carry costs, such as distance or time

For a directed graph, A → B does not also give you B → A. The direction belongs to the problem, not to the traversal algorithm.

A graph can be hidden in a question

A maze may not be described as a graph. Still, each walkable cell is a node, and each allowed move is an edge. A word-transformation question has words as nodes and legal one-letter changes as edges.

The useful question is: What is my current state, and which states can I move to next?

2. BFS and DFS in one picture

BFS explores nearby nodes first. On our example, starting at A:

Worked example · read from top to bottom
Distance 0: A
Distance 1: B, C
Distance 2: D, E, F, G

BFS order: A, B, C, D, E, F, G

DFS explores one branch deeply before returning. With neighbors considered left to right:

Worked example · read from top to bottom
A → B → D
        return to B → E
return to A → C → F
                 return to C → G

DFS entry order: A, B, D, E, C, F, G

On the same seven-node tree, BFS processes distance layers A, then B and C, then D through G. DFS follows A-B-D, returns to B for E, then explores C-F and C-G.

These orders are not universal answers. If you change the starting node or neighbor order, the traversal order can change. BFS still keeps its distance-layer property, and DFS still completes a branch before returning to the caller.

3. The queue and stack decide what happens next

BFS uses a queue: first in, first out

Think of people waiting in a line. The first person to join is the first person served.

Worked example · read from top to bottom
FRONT                             REAR
remove here ← [B] [C] [D] ← add here

Add at the rear. Remove from the front. This is FIFO, or first in, first out.

After BFS processes A, B and C wait in that order. Processing B adds D and E behind C. C still gets its turn before D or E. That is how the queue preserves layers.

DFS uses a stack: last in, first out

Think of plates stacked on a table. The newest plate goes on top and is taken off first.

Worked example · read from top to bottom
        push ↓  ↑ pop
TOP     dfs(D)       active call
        dfs(B)       paused call
BOTTOM  dfs(A)       oldest call

Both push and pop happen at the top. This is LIFO, or last in, first out.

Recursion already gives you a stack: Java maintains the call stack. You can also manage an explicit stack yourself using Deque.

A FIFO queue adds at the rear and removes at the front. A LIFO call stack pushes and pops at the top, with dfs(D) above paused dfs(B) and dfs(A).

A recursive stack frame is more than a node name. It remembers local variables and where the method should resume after its child call returns. The explicit-frame Java code below stores that saved neighbor position as a cursor.

4. Dry run: one graph, two work lists

Use the branching graph above and follow the queue or active calls on paper. BFS keeps pending discoveries in FIFO order; recursive DFS finishes a child before resuming the next neighbor. The complete BFS table and Java methods below provide the exact states.

Question to ask at each Java instruction BFS Recursive DFS
What work is chosen next? Remove the oldest queued node Continue the newest active frame
What is remembered? Discovered nodes, parents and distances Discovered nodes and the next neighbor in each waiting call
When is a neighbor marked? Before enqueueing it Before recursing into it
What happens after a dead end? Process the next queued node Return to the paused parent frame

Try an edge back to an already discovered node: both versions skip that visit, avoiding cycles. Then add an isolated node: neither reaches it from another component. An outer loop starts a new traversal there.

5. Represent the graph in Java

An adjacency list stores the neighbors of each node. For our example:

Worked example · read from top to bottom
0 (A): [1, 2]
1 (B): [0, 3, 4]
2 (C): [0, 5, 6]
3 (D): [1]
4 (E): [1]
5 (F): [2]
6 (G): [2]

We use List<List<Integer>>. graph.get(node) gives that node’s neighbor list.

For an undirected edge, add each endpoint to the other’s list. For a directed edge, add only the outgoing neighbor.

An adjacency list needs O(V + E) memory, where V is the number of vertices and E is the number of edges. An undirected edge appears twice, but multiplying by two does not change Big O.

An adjacency matrix uses a V-by-V table. It makes an edge lookup simple, but uses O(V²) memory, and finding a node’s neighbors requires scanning its row. The O(V + E) traversal bounds in this guide assume adjacency lists, not matrices.

Runnable companion and assumptions

Download the complete Java examples. The file contains the imports, graph builder, all methods, and a main method. Run it locally with:

Worked example · read from top to bottom
javac BfsDfsExamples.java
java BfsDfsExamples

The excerpts below belong inside that class. Nodes use valid IDs from 0 to graph.size() - 1. checkStart rejects an invalid start. An empty graph has no valid starting node, although counting its components returns zero. These examples do not accept null graphs or null grid rows.

The same ArrayDeque implementation can be used through different contracts. The Java Deque documentation describes its queue and stack operations. Use offer/poll for a queue and push/pop for a stack; mixing the two sets can silently change the ordering you intended.

6. BFS approach using a queue

We need three things:

  • A queue of nodes waiting to be processed.
  • A way to know which nodes were already discovered.
  • A distance for each discovered node, if shortest paths matter.

Here, distance[node] == -1 also means “not discovered yet.” We do not need a separate visited array.

Java
public record BfsResult(List<Integer> order, int[] distance, int[] parent) {}

public static BfsResult bfs(List<List<Integer>> graph, int start) {
    checkStart(graph, start);
    int[] distance = new int[graph.size()];
    int[] parent = new int[graph.size()];
    Arrays.fill(distance, -1);
    Arrays.fill(parent, -1);
    List<Integer> order = new ArrayList<>();
    Queue<Integer> queue = new ArrayDeque<>();

    distance[start] = 0;
    queue.offer(start);

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

        for (int next : graph.get(node)) {
            if (distance[next] == -1) {
                distance[next] = distance[node] + 1;
                parent[next] = node;
                queue.offer(next);
            }
        }
    }
    return new BfsResult(order, distance, parent);
}

parent[next] = node records who first discovered next. Later, it lets us reconstruct a shortest path.

BFS dry run

The queue is shown front first. Each row records the state after processing one node’s neighbors; compare it with removeFirst() and addLast() in the Java code.

Operation Queue afterwards New discoveries
Discover and enqueue A A A at distance 0
Dequeue A B, C B, C at distance 1
Dequeue B C, D, E D, E at distance 2
Dequeue C D, E, F, G F, G at distance 2
Dequeue D E, F, G None
Dequeue E F, G None
Dequeue F G None
Dequeue G Empty None

When B sees A, it skips A because A was already discovered. The two-way edge must not send us back and forth forever.

Why mark a node before adding it to the queue?

Suppose both B and C point to D. If we wait until D leaves the queue to mark it, B can enqueue D, then C can enqueue D again.

Marking D at discovery time means “D is already scheduled.” Every node then enters the queue at most once. A discovered node may still be waiting; discovered and processed are different ideas.

Why is the distance the shortest?

The queue processes distance 0 before distance 1, distance 1 before distance 2, and so on. A node first discovered from a distance-d node receives distance d + 1. A shorter route would have come from an earlier layer and would already have discovered it.

This proves the fewest-edges result for an unweighted graph, not a minimum-cost result for arbitrary weights. Princeton’s BFS treatment discusses this shortest-path property.

Get the path, not just its length

Walk backwards through parent, then reverse the result:

Java
public static List<Integer> pathTo(BfsResult result, int target) {
    if (target < 0 || target >= result.distance().length)
        throw new IllegalArgumentException("Invalid target");
    if (result.distance()[target] == -1) return List.of();
    List<Integer> path = new ArrayList<>();
    for (int node = target; node != -1; node = result.parent()[node])
        path.add(node);
    Collections.reverse(path);
    return path;
}

For G, the IDs are [0, 2, 6], meaning A → C → G, with two edges. If the target is not reachable, the returned path is empty. If the target is the start, the path contains just the start and its distance is zero.

7. DFS approach using recursion

DFS says: “Enter this node. Explore one unseen neighbor completely. Come back and continue with the next neighbor.”

Java
public static List<Integer> dfsRecursive(List<List<Integer>> graph, int start) {
    checkStart(graph, start);
    boolean[] visited = new boolean[graph.size()];
    List<Integer> order = new ArrayList<>();
    visit(graph, start, visited, order);
    return order;
}

private static void visit(List<List<Integer>> graph, int node,
                          boolean[] visited, List<Integer> order) {
    visited[node] = true;
    order.add(node);
    for (int next : graph.get(node)) {
        if (!visited[next]) visit(graph, next, visited, order);
    }
}

The method does not create its own queue. A recursive call puts a new frame on Java’s call stack. The caller pauses until that call returns.

What exactly happens to the call stack?

This table shows the top frame first.

Event Call stack Meaning
Enter A A Start exploring A
A calls B B, A A pauses
B calls D D, B, A B pauses; D runs
D finishes B, A D pops; B resumes
B calls E E, B, A Explore B’s next unseen neighbor
E finishes, then B finishes A A resumes
A calls C C, A Start the other branch

There is no jump from D straight to C. D returns to B first. B must finish its remaining work before returning to A.

Where is the base case?

For this graph DFS, there is no unseen neighbor left to call. The loop finishes and the method returns. The visited check prevents cycles from generating endless calls.

Each successful recursive call discovers a previously unseen node. The graph is finite, so at most V such calls can be active or completed during one full traversal.

Why not remove a node from visited when returning?

Ordinary traversal asks whether we have ever discovered the node. Once discovered, it stays discovered.

Backtracking answers a different question: is the node in the current candidate path? That temporary path state may be removed on return. Confusing permanent traversal state with temporary path state is a common source of bugs.

For a long chain, recursive DFS can cause StackOverflowError in Java. There is no universally safe maximum depth: stack size and frame size matter. Use an explicit stack when depth may be large.

8. DFS approach using an explicit stack

There are two useful stack implementations. They store different things, so they deserve separate explanations.

A simple stack of pending nodes

Java
public static List<Integer> dfsPendingStack(List<List<Integer>> graph, int start) {
    checkStart(graph, start);
    boolean[] visited = new boolean[graph.size()];
    List<Integer> order = new ArrayList<>();
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);

    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (visited[node]) continue;
        visited[node] = true;
        order.add(node);
        List<Integer> neighbors = graph.get(node);
        for (int i = neighbors.size() - 1; i >= 0; i--) {
            int next = neighbors.get(i);
            if (!visited[next]) stack.push(next);
        }
    }
    return order;
}

We push neighbors in reverse order because the last push is the first pop. To process B before C, push C and then B.

This version marks nodes when they are popped. Multiple pending copies can exist before the first pop; the guard discards later copies. It remains correct, but its pending stack can need O(E) space in the worst case. Along with visited and output, the bound is O(V + E).

You may also see versions marking nodes when pushed. They avoid pending duplicates, but eagerly scheduling all neighbors can produce a different discovery tree or order from recursive DFS on graphs with cross-links. Do not assume every “replace queue with stack” implementation is an exact simulation of recursion.

A frame stack that behaves like recursion

To reproduce recursive DFS precisely, remember where each paused call should resume:

Java
private static class Frame {
    final int node;
    int next;
    Frame(int node) { this.node = node; }
}

public static List<Integer> dfsStack(List<List<Integer>> graph, int start) {
    checkStart(graph, start);
    boolean[] visited = new boolean[graph.size()];
    List<Integer> order = new ArrayList<>();
    Deque<Frame> stack = new ArrayDeque<>();
    visited[start] = true;
    order.add(start);
    stack.push(new Frame(start));

    while (!stack.isEmpty()) {
        Frame frame = stack.peek();
        if (frame.next == graph.get(frame.node).size()) {
            stack.pop();
            continue;
        }
        int next = graph.get(frame.node).get(frame.next++);
        if (!visited[next]) {
            visited[next] = true;
            order.add(next);
            stack.push(new Frame(next));
        }
    }
    return order;
}

peek() reads the top without removing it. frame.next++ saves the caller’s next neighbor position before we push the child. When the child pops, the parent frame is still there with the correct resume position.

This explicit-frame implementation is the static equivalent of the recursive call stack. It has the same entry order as recursive DFS for the same graph, start, and neighbor order, including graphs with cycles.

9. BFS versus DFS: when should you choose which?

Need Usually start with Reason
Fewest moves, all moves cost the same BFS Processes distance layers
Level-by-level tree output BFS A layer is already a queue boundary
Reachability or undirected components Either Both explore everything reachable
Simultaneous spread from many starts Multi-source BFS All starting points belong to distance 0
Child results before parent result DFS postorder A call resumes after its children
Explore choices and undo them DFS/backtracking The current path is naturally available
Very deep graph Iterative BFS or DFS Avoids JVM recursive-stack overflow
Weighted minimum-cost path Not ordinary BFS Use an algorithm that respects edge costs

DFS can find a path, but the first path it finds need not be shortest. BFS is not always “better” or “faster”: both basic traversals have the same asymptotic running time with adjacency lists. Choose by the result and invariant, not by a favorite template.

10. Disconnected graphs: one start is not the whole graph

Suppose the graph contains A-B-C, D-E, and isolated F. A traversal starting at A reaches only A, B, and C.

For an undirected graph, an outer loop starts a new search at every still-unvisited node. Every new search marks one connected component.

Java
public static int countComponents(List<List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    int components = 0;
    for (int node = 0; node < graph.size(); node++) {
        if (!visited[node]) {
            components++;
            visit(graph, node, visited, new ArrayList<>());
        }
    }
    return components;
}

The visited array is shared across the outer loop. Do not reset it for each start. This example returns three components, counting isolated F as one component.

For a directed graph, “component” is not this simple. Weak connectivity ignores arrow direction; strong connectivity requires mutual reachability following arrows. An ordinary outer-loop DFS forest is not a strongly connected components algorithm. Kosaraju and Tarjan address that separate problem.

11. How to recognize a BFS or DFS question

Do not search only for the words graph, BFS, or DFS. First identify the structure:

  1. State: What does one node represent?
  2. Moves: Which next states are legal?
  3. Goal: Reach somewhere, count groups, find a shortest route, detect a cycle, or enumerate possibilities?
  4. Cost: Does every move cost the same?
  5. Visited key: Is the state just a node, or does it include extra information?

Here are useful signals, with the reasoning behind them:

Question language What to investigate
“minimum steps,” “fewest moves,” “nearest” BFS if every legal move has equal cost
“level,” “layer,” “each minute,” “spreads simultaneously” BFS layers, possibly multiple starting points
“islands,” “regions,” “groups,” “connected” Flood fill or connected components
“can reach,” “is there a path” BFS or DFS reachability
“prerequisites,” “dependency,” “can finish all tasks” Directed cycles and topological ordering
“two groups,” “opposite sides,” “no same-group edge” Bipartite coloring
“all paths,” “all choices,” “undo” DFS with path-local backtracking
“subtree,” “after processing children” DFS postorder and subtree aggregation

These are clues, not proofs. “Minimum” could mean a weighted path, dynamic programming, or binary search. Check the state and edge costs before choosing BFS.

Sometimes the visited state needs more dimensions

In a maze where you may break one wall, reaching (row, column) with your wall break unused is different from reaching it after using the break.

The state is (row, column, breaksUsed), so the visited key must include all three parts. Marking only the cell can discard a useful route. The same idea appears with keys, remaining fuel, direction, or a time phase.

Complexity follows the number of states and transitions, not just the number of visible cells.

12. Twelve practical pattern families

There is no official fixed number of BFS and DFS patterns. Authors group overlapping ideas differently. These 12 families form a useful learning checklist, not a claim that every question fits exactly one box.

Family Typical signal Main idea Extra state
1. Reachability Can A reach B? Explore unseen neighbors Visited
2. Connected components How many groups? Outer loop + flood fill Shared visited, count
3. Level-order processing Output each level Process the current queue size Current level
4. Unweighted shortest paths Fewest equal-cost moves First discovery gives distance Distance, parent
5. Multi-source BFS Nearest source or simultaneous spread Enqueue every source first Distance, all starts
6. Grid flood fill Islands, areas, enclosed cells Treat cells as nodes Bounds, legal directions
7. Undirected cycle detection Does a loop exist? Ignore the parent edge Parent or edge ID
8. Directed cycle detection Can dependencies loop? Edge to an active DFS call Unseen/active/finished state
9. Bipartite coloring Can nodes form two groups? Give neighbors opposite colors Color
10. Topological ordering Which task must come first? Finish-order DFS or Kahn’s queue Cycle state or indegree
11. Path enumeration List every valid route Choose, explore, undo Current path, path-local visited
12. Postorder aggregation Use child answers at parent Combine after child returns Child results, parent

The next sections explain the important adjustments. Do not memorize 12 unrelated programs. Most are the same traversal plus one extra rule or piece of state.

13. Level-order and multi-source BFS

Process a whole level

When the question wants results grouped by level, capture the queue size before processing that level. Remove exactly that many nodes. New children belong to the next level.

Worked example · read from top to bottom
while queue is not empty:
    levelSize = queue.size()
    repeat levelSize times:
        node = remove from front
        record node in this level
        discover and enqueue its unseen neighbors
    finish this level

If you use the changing queue size as the loop condition, newly added nodes can slip into the current level. On a tree, level order is A, then [B, C], then [D, E, F, G]. On a graph, remember visited state too.

Start from several sources at once

If fire starts at three cells simultaneously, do not run three separate searches and add their times. Put all three sources into the queue with distance zero before processing any source.

Java
public static int[] multiSourceDistances(List<List<Integer>> graph, int[] sources) {
    int[] distance = new int[graph.size()];
    Arrays.fill(distance, -1);
    Queue<Integer> queue = new ArrayDeque<>();
    for (int source : sources) {
        checkStart(graph, source);
        if (distance[source] == -1) {
            distance[source] = 0;
            queue.offer(source);
        }
    }
    while (!queue.isEmpty()) {
        int node = queue.poll();
        for (int next : graph.get(node)) {
            if (distance[next] == -1) {
                distance[next] = distance[node] + 1;
                queue.offer(next);
            }
        }
    }
    return distance;
}

Each answer is the distance from the nearest source, following edge direction if the graph is directed. Duplicate sources are scheduled once. With no sources, every distance stays -1.

Rotting Oranges is a classic simultaneous-spread exercise. Binary Tree Level Order Traversal practices the level boundary.

14. Grids are graphs without an explicit neighbor list

In an islands question, each land cell is a node. Adjacent land cells are connected. Usually the four moves are up, down, left, and right, but the problem may allow eight directions instead.

Worked example · read from top to bottom
1 1 0
0 1 0
1 0 1

With four-direction movement, this grid has three islands. The diagonal cells do not connect.

To count islands:

  1. Scan every cell.
  2. If a cell is unseen land, start a new island.
  3. Use BFS or DFS to mark all land reachable from it.
  4. Continue the scan, skipping land already marked.

The companion’s countIslands method uses a queue and a separate seen grid. It does not change the input. Its critical neighbor rule is:

Worked example · read from top to bottom
next cell is inside the grid
AND next cell is land
AND next cell has not been discovered
→ mark it first, then enqueue it

Some solutions change land to water to act as visited state. That can avoid a separate seen grid, but changes the caller’s input and still needs queue or stack memory. Say clearly whether mutation is allowed.

For R rows and C columns with a constant number of movement directions, traversal costs O(R × C) time and at most O(R × C) auxiliary memory.

Try Number of Islands after understanding the scan plus flood fill. Follow its specific movement rules; do not assume diagonals count.

15. Cycles: undirected and directed rules are different

Undirected graph: ignore the edge back to the parent

If DFS moves from A to B, B sees A in its neighbor list. That edge is not a new cycle; it is the same edge we just followed in reverse.

For a simple undirected graph, track the parent. A neighbor that was visited and is not the parent indicates a cycle. Self-loops are cycles. If parallel edges are allowed, tracking only a parent node can hide a two-edge cycle; track the actual parent edge ID instead.

Directed graph: track active calls, not just visited nodes

In a directed graph, an edge to an already finished node does not necessarily indicate a cycle. For example, A → B, A → C, C → B can be acyclic even though B was visited before C checks it.

Use three states:

Worked example · read from top to bottom
0 = unseen
1 = active in the current DFS path
2 = finished

An edge to state 1 points back into the current active path and closes a directed cycle. An edge to state 2 can be skipped safely.

Java
public static boolean hasDirectedCycle(List<List<Integer>> graph) {
    int[] state = new int[graph.size()];
    for (int node = 0; node < graph.size(); node++) {
        if (state[node] == 0 && cycleFrom(graph, node, state)) return true;
    }
    return false;
}

private static boolean cycleFrom(List<List<Integer>> graph, int node, int[] state) {
    state[node] = 1;
    for (int next : graph.get(node)) {
        if (state[next] == 1) return true;
        if (state[next] == 0 && cycleFrom(graph, next, state)) return true;
    }
    state[node] = 2;
    return false;
}

If a prerequisite relation forms a cycle, no valid completion order exists. That is the key observation behind Course Schedule.

16. Bipartite graphs and topological ordering

Two-coloring: every edge must cross groups

Pick a color for the start node. Give each unseen neighbor the opposite color. If an edge connects two nodes with the same color, the graph is not bipartite.

Run this rule for every disconnected component. A conflict in one component makes the whole graph fail.

The companion includes the complete isBipartite queue implementation. It returns true for an even cycle and false for a triangle or self-loop. An undirected graph is bipartite exactly when it has no odd cycle. Practice with Is Graph Bipartite?.

Dependencies: BFS-like queue or DFS finish order

A topological order places every prerequisite before the task that depends on it. It exists only for a directed acyclic graph, often called a DAG.

Two standard approaches are:

  • Kahn’s algorithm: calculate each node’s indegree, which counts incoming edges. Queue all indegree-zero nodes. Remove one, output it, and decrement the indegrees of its outgoing neighbors. Add a neighbor when its indegree reaches zero. If fewer than V nodes are output, a cycle remains.
  • DFS: detect directed cycles using active/finished state. Add each node after its outgoing neighbors finish, then reverse that finish order. The reverse is valid only if no cycle was found.

Kahn’s algorithm uses a queue, but its invariant is “no remaining prerequisites,” not ordinary BFS distance layers. Seeing a queue in a solution does not automatically mean unweighted shortest-path BFS.

For prerequisites represented as [task, prerequisite], the edge for ordering should be prerequisite → task. Reversing that meaning can reverse the intended answer.

17. DFS on trees, backtracking, and child results

Preorder, inorder, and postorder

For a rooted binary tree:

Order When to process the node Typical use
Preorder Before left and right children Record the root before descendants
Inorder Between left and right children Sorted values of a valid binary search tree
Postorder After both children Height, subtree sizes, delete/free descendants first

Inorder is specifically a left-node-right convention for binary trees. General graphs do not have an inherent left and right child.

A true tree traversed through child pointers has no cycles, so it often needs no visited set. If an undirected tree is stored as an adjacency list, skip the parent edge or use visited, because each edge appears in both directions.

A child result is available only after the call returns

For subtree height, recursively calculate the children’s heights, then combine them at the parent. That is postorder work. Processing a parent immediately on entry is not enough when its answer depends on children.

For a DAG, overlapping descendants may need memoization to avoid repeated work. For a cyclic graph, a simple subtree recurrence may not even be well-defined. First identify the structure.

Enumerating paths is not ordinary “visit each node once”

Suppose two different routes reach the same node and you must list both. A global visited set may incorrectly discard the second route.

To enumerate simple paths, mark nodes in the current path, explore a choice, and remove that mark when returning. Copy the path when saving a result; otherwise later changes can alter previously saved answers.

In a cyclic graph, unrestricted walks can be infinite. Define whether repeated nodes are allowed and what makes a path stop. Path enumeration can be exponential or worse in output size; it does not inherit the O(V + E) bound of basic visited-once traversal.

The Subsets explanation develops the same choose, explore, undo idea in a different setting.

18. Important variants to learn next

You do not need all of these to start solving basic graph questions. Know the boundary so you do not apply the wrong template.

Variant What changes
0–1 BFS Edges cost only 0 or 1. Use a deque, add zero-cost improvements at the front and one-cost improvements at the rear, and relax distances rather than blindly using “seen once.”
Dijkstra Nonnegative weighted edges. A priority queue selects the smallest tentative distance. An ordinary FIFO queue is not enough.
Bellman-Ford Handles negative edge weights and can detect reachable negative cycles. Different complexity and stopping guarantees apply.
Bidirectional BFS Search from both endpoints for a single unweighted shortest path. Directed graphs need reverse edges on the target side, and stopping must respect complete-layer/frontier conditions.
Iterative deepening DFS Repeat depth-limited DFS with increasing limits. Useful when solution depth is unknown and frontier memory is expensive, but repeated work and cycle handling need care.
Strongly connected components Kosaraju or Tarjan group mutually reachable nodes in directed graphs. Not the same as ordinary component counting.
Bridges and articulation points DFS discovery times and low-link values reveal connections whose removal splits an undirected graph.

These deserve separate worked articles. This guide gives the foundations and recognition map; it does not claim to fully implement every advanced graph algorithm.

19. Time and space complexity without shortcuts

For adjacency lists, a full basic traversal examines each discovered node and its neighbor list. Across the whole graph, that is O(V + E) time.

Approach Time for a full traversal Working memory, excluding graph and returned output
BFS with queue O(V + E) O(V) for discovery/distance and queue
Recursive DFS O(V + E) O(V) visited plus up to O(V) call frames
Explicit-frame DFS O(V + E) O(V) visited plus up to O(V) frames
Pending-node DFS shown above O(V + E) O(V + E), because pending duplicates may accumulate

The graph itself needs O(V + E) space. Returning an order, distances, parents, or a path also uses space; do not label it “free.” Array initialization costs O(V), even if a search reaches only one small component.

For a tree, E = V - 1, so traversal is O(V). BFS frontier size can grow with the tree’s maximum width; recursive DFS stack depth grows with its height. The total auxiliary memory still includes any visited arrays used by the implementation.

For an adjacency matrix, neighbor scanning can take O(V²) in a full traversal. For an implicit-state problem, count the generated states and transitions. For enumerating paths, count the output too.

20. Common mistakes and a debugging checklist

Mistake Why it fails What to check
No visited state in a cyclic graph Nodes send the search around the cycle forever Mark discovery and skip repeats
Mark BFS only when dequeued Several parents may schedule the same node Mark before enqueue
Use stack operations for BFS Newest work runs before the older layer Queue uses offer/poll
Claim DFS’s first path is shortest Deep exploration can take a long detour first Use BFS for equal-cost shortest paths
Reset visited inside the outer loop A component is repeatedly explored and counted Share visited across roots
Use ordinary visited for directed cycle detection Edges to finished nodes can look like cycles Distinguish active from finished
Forget edge direction The traversal invents moves not allowed by the problem Add reverse edges only when undirected
Forget isolated nodes Edge input alone may omit them Create all V node lists first
Ignore part of the state A useful route is incorrectly pruned Include keys, fuel, wall breaks, or time phase
Clear global visited while returning Ordinary traversal repeatedly rediscovers nodes Undo only path-local backtracking state
Recursive DFS on a huge chain JVM call stack may overflow Use an explicit frame stack

When an answer looks wrong, write down the current node, queue or stack, discovered nodes, and the next legal neighbor. A short trace often reveals the bug faster than staring at the full program.

21. Edge cases worth testing

Test more than the seven-node tree:

  • One isolated node: its BFS distance is 0; both traversals output it once.
  • No edges: one start reaches only itself; an undirected component count equals V.
  • A disconnected graph: unreachable distances remain -1.
  • A cycle and a self-loop: ordinary traversal must terminate without duplicate output.
  • Two parents sharing a child: BFS must enqueue the child once.
  • Directed edges: a reverse route may not exist.
  • A long chain: iterative methods should work without recursive depth risk.
  • Multiple shortest routes: distance is stable, but the chosen parent path may depend on neighbor order.
  • Grid corners, one row, all water, and diagonal-only land: movement rules determine the answer.
  • An even cycle and an odd cycle: they differ under bipartite coloring.

The downloadable Java file is checked with branching graphs, isolated nodes, cycles, directed edges and disconnected components. Apply the same queue/stack tables to each case: discovery marks and frame return order determine the result.

22. A sensible practice order

  1. Trace the branching tree by hand, then compare with the BFS table and recursive call sequence.
  2. Write BFS traversal and recursive DFS without looking at the code.
  3. Implement explicit-frame DFS and explain what the frame’s cursor means.
  4. Count undirected components and grid islands.
  5. Find unweighted shortest distances and reconstruct a path.
  6. Process tree levels and multi-source spreading.
  7. Detect directed cycles, color bipartite graphs, and learn topological sorting.
  8. Try implicit-state searches, such as Word Ladder.
  9. Only then move to weighted paths, SCCs, low-link algorithms, and other advanced variants.

For Word Ladder, a word is a state and a permitted one-letter transformation is an edge. The question counts words in the sequence, not just edges. Understand that counting convention before returning the BFS distance.

Do not memorize a problem name and its algorithm. For every attempt, say out loud: “My node is ___. My legal move is ___. My visited state is ___. I need ___ as the answer.”

23. Final takeaway

BFS asks what is closest in number of moves. DFS asks what lies deeper along the current branch. A queue makes older discoveries run first. A stack makes the newest active work run first.

Both need correct neighbor generation and correct discovery state. Many question patterns are simply these traversals plus distances, parents, colors, active-call state, or a path to undo.

If you can explain what is stored, when it is added, when it is removed, and why a node is skipped, you understand the algorithm well enough to adapt it.

References and continue learning

Practice next

Next lessonStepping Numbers in Java: Grow a Digit Tree Instead of Scanning a Range

Generate sorted stepping numbers with digit-based DFS, boundary checks, safe arithmetic, an actual recursion tree, and beginner-friendly Java explanations.

Back to Graphs →