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:
A
/ \
B C
/ \ / \
D E F GThe 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:
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:
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, GThese 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.
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.
push ↓ ↑ pop
TOP dfs(D) active call
dfs(B) paused call
BOTTOM dfs(A) oldest callBoth 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 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:
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:
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.
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:
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.”
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
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:
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.
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:
- State: What does one node represent?
- Moves: Which next states are legal?
- Goal: Reach somewhere, count groups, find a shortest route, detect a cycle, or enumerate possibilities?
- Cost: Does every move cost the same?
- 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.
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 levelIf 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.
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.
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:
- Scan every cell.
- If a cell is unseen land, start a new island.
- Use BFS or DFS to mark all land reachable from it.
- 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:
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:
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.
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
- Trace the branching tree by hand, then compare with the BFS table and recursive call sequence.
- Write BFS traversal and recursive DFS without looking at the code.
- Implement explicit-frame DFS and explain what the frame’s cursor means.
- Count undirected components and grid islands.
- Find unweighted shortest distances and reconstruct a path.
- Process tree levels and multi-source spreading.
- Detect directed cycles, color bipartite graphs, and learn topological sorting.
- Try implicit-state searches, such as Word Ladder.
- 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
- Princeton: Undirected Graphs provides the graph representation and basic traversal background.
- Princeton: Directed Graphs covers dependencies, cycles, topological order, and strong connectivity.
- Java 21: Deque documents queue and stack operations.
- Recursion in Java explains paused calls and returns.
- Subsets in Java shows how DFS-style exploration becomes backtracking.
- Graph topics is the home for this guide and future graph lessons.
Practice next
Next lessonStepping Numbers in Java: Grow a Digit Tree Instead of Scanning a RangeGenerate sorted stepping numbers with digit-based DFS, boundary checks, safe arithmetic, an actual recursion tree, and beginner-friendly Java explanations.