Quick answer
Breadth-first search (BFS) explores a graph level by level using a queue. It finds minimum-edge paths in an unweighted graph. Depth-first search (DFS) follows one branch as far as possible before backtracking, using recursion or an explicit stack. It is often convenient for reachability, components, cycle reasoning, and dependency-style traversals.
Both run in O(V + E) time with an adjacency list and use O(V) auxiliary space. Choose based on the guarantee you need, not on which template you remember.
Model the graph first
A graph has vertices and edges. Edges may be directed or undirected, weighted or unweighted, simple or duplicated. Traversal behavior depends on that contract.
An adjacency list stores outgoing neighbors for each vertex:
Map<String, List<String>> graph = Map.of(
"A", List.of("B", "C"),
"B", List.of("D"),
"C", List.of("D", "E"),
"D", List.of(),
"E", List.of()
);For an undirected edge, add both directions. For a directed edge, add only the declared direction. Include vertices with no outgoing edges so callers can distinguish a known isolated vertex from an unknown key.
Neighbor order is not a graph property unless the API says so. If tests or user output require deterministic traversal, preserve insertion order or sort copied neighbor lists.
BFS intuition
BFS starts with a source at distance zero. It processes every vertex at distance d before any vertex at distance d + 1.
queue [A]
visit A -> enqueue B,C
queue [B,C]
visit B -> enqueue D
queue [C,D]
visit C -> D already discovered, enqueue E
queue [D,E]The first time BFS discovers a vertex in an unweighted graph, it has found a path with the minimum number of edges. Any shorter path would have reached that vertex from an earlier level.
Java BFS implementation
Mark a vertex visited when it is enqueued, not later when dequeued. That prevents multiple parents from adding the same vertex:
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
static <V> List<V> bfs(Map<V, List<V>> graph, V start) {
if (graph == null || start == null) {
throw new IllegalArgumentException("graph and start are required");
}
if (!graph.containsKey(start)) {
throw new IllegalArgumentException("start vertex is not in graph");
}
List<V> order = new ArrayList<>();
Set<V> visited = new HashSet<>();
ArrayDeque<V> queue = new ArrayDeque<>();
visited.add(start);
queue.addLast(start);
while (!queue.isEmpty()) {
V current = queue.removeFirst();
order.add(current);
for (V neighbor : graph.getOrDefault(current, List.of())) {
if (visited.add(neighbor)) {
queue.addLast(neighbor);
}
}
}
return List.copyOf(order);
}ArrayDeque provides FIFO behavior through addLast and removeFirst. It prohibits null, so the graph contract should reject null vertices or map them before traversal.
BFS shortest paths
Store a predecessor when discovering each vertex:
static <V> Map<V, V> bfsParents(
Map<V, List<V>> graph,
V start) {
Map<V, V> parent = new HashMap<>();
Set<V> visited = new HashSet<>();
ArrayDeque<V> queue = new ArrayDeque<>();
visited.add(start);
queue.addLast(start);
while (!queue.isEmpty()) {
V current = queue.removeFirst();
for (V neighbor : graph.getOrDefault(current, List.of())) {
if (visited.add(neighbor)) {
parent.put(neighbor, current);
queue.addLast(neighbor);
}
}
}
return parent;
}Follow parent backward from a target to reconstruct the path, then reverse it. If the graph has edge weights, ordinary BFS is correct only when every edge has the same cost. Use Dijkstra’s algorithm for nonnegative unequal weights and other algorithms when negative weights exist.
DFS intuition
DFS maintains a frontier of unfinished branches:
start A
go B
go D
backtrack to B, then A
go C
D already visited
go ERecursive DFS mirrors this description, but the Java call stack can overflow on a deep graph. An iterative stack is safer for untrusted or production-scale depth.
Recursive Java DFS
static <V> List<V> dfsRecursive(
Map<V, List<V>> graph,
V start) {
List<V> order = new ArrayList<>();
Set<V> visited = new HashSet<>();
visit(graph, start, visited, order);
return List.copyOf(order);
}
private static <V> void visit(
Map<V, List<V>> graph,
V current,
Set<V> visited,
List<V> order) {
if (!visited.add(current)) {
return;
}
order.add(current);
for (V neighbor : graph.getOrDefault(current, List.of())) {
visit(graph, neighbor, visited, order);
}
}This is concise and useful when maximum depth is bounded. The visited set prevents infinite recursion on cycles and self-loops.
Iterative Java DFS
static <V> List<V> dfsIterative(
Map<V, List<V>> graph,
V start) {
List<V> order = new ArrayList<>();
Set<V> visited = new HashSet<>();
ArrayDeque<V> stack = new ArrayDeque<>();
stack.addLast(start);
while (!stack.isEmpty()) {
V current = stack.removeLast();
if (!visited.add(current)) {
continue;
}
order.add(current);
List<V> neighbors = graph.getOrDefault(current, List.of());
for (int i = neighbors.size() - 1; i >= 0; i--) {
V neighbor = neighbors.get(i);
if (!visited.contains(neighbor)) {
stack.addLast(neighbor);
}
}
}
return List.copyOf(order);
}Neighbors are pushed in reverse so the first listed neighbor is processed first, matching recursive preorder. Marking on pop may add duplicates to the stack; marking on push prevents duplicates but changes how parent/cycle state is recorded. Choose one policy and prove it for the task.
BFS versus DFS
Use BFS when:
- you need minimum edges in an unweighted graph;
- the target is expected near the source;
- level order matters;
- you are expanding states by number of moves;
- you need all vertices within
khops.
Use DFS when:
- any path or reachability answer is enough;
- you need connected components;
- recursive entry/exit times help;
- you are exploring all combinations with backtracking;
- the solution depends on finishing a branch;
- memory should track depth rather than a potentially wide level.
BFS can hold an entire wide frontier. DFS can hold a very deep path. Both worst-case auxiliary bounds are O(V).
Connected components
A traversal from one source reaches only its component. To cover an undirected graph:
static <V> int countComponents(Map<V, List<V>> graph) {
Set<V> visited = new HashSet<>();
int components = 0;
for (V vertex : graph.keySet()) {
if (visited.contains(vertex)) {
continue;
}
components++;
ArrayDeque<V> stack = new ArrayDeque<>();
stack.addLast(vertex);
while (!stack.isEmpty()) {
V current = stack.removeLast();
if (!visited.add(current)) continue;
for (V neighbor : graph.getOrDefault(current, List.of())) {
if (!visited.contains(neighbor)) stack.addLast(neighbor);
}
}
}
return components;
}For directed graphs, “component” is ambiguous: weakly connected and strongly connected components require different definitions and algorithms.
Cycle detection is graph-specific
A visited neighbor does not always mean a cycle.
In an undirected graph, an edge back to the immediate parent is expected. Detect a cycle when a visited neighbor is not the parent.
In a directed graph, use states such as unvisited, visiting, and finished. An edge to a currently visiting vertex is a back edge and proves a directed cycle. An edge to a finished vertex does not.
Traversal is the engine, while the extra state determines the result.
Topological ordering boundary
DFS finishing order can produce a topological ordering for a directed acyclic graph. Kahn’s algorithm uses BFS-like processing of zero-indegree vertices. Both must detect cycles; returning a partial order without an error is unsafe for dependency execution.
Do not describe ordinary DFS preorder as a topological sort. The order is based on finish times, typically reversed after recursion completes.
Trees and grids are graphs
A tree traversal can omit a general visited set if every node has one parent and code never follows the parent edge back. Input that might contain cycles still needs protection.
A grid becomes a graph where cells are vertices and allowed moves are edges. BFS finds the fewest moves in an unweighted maze. DFS is useful for marking islands or regions. Bounds checks and obstacle rules are the adjacency function.
Generating neighbors on demand avoids building a large explicit graph.
Complexity
With an adjacency list:
- every reachable vertex is discovered once;
- every outgoing adjacency entry is examined once;
- BFS and DFS time are
O(V + E); - visited state plus queue/stack is
O(V).
For an undirected graph stored in both directions, there are 2E adjacency entries, which is still O(E).
With an adjacency matrix, checking every possible neighbor for every visited vertex costs O(V²), even for a sparse graph. Always state the representation behind the complexity claim.
Testing traversal code
@Test
void bfsUsesLevelOrderAndDoesNotRepeatDiamondVertex() {
Map<String, List<String>> graph = Map.of(
"A", List.of("B", "C"),
"B", List.of("D"),
"C", List.of("D"),
"D", List.of()
);
assertEquals(List.of("A", "B", "C", "D"), bfs(graph, "A"));
}
@Test
void dfsHandlesCycleAndSelfLoop() {
Map<Integer, List<Integer>> graph = Map.of(
1, List.of(1, 2),
2, List.of(3),
3, List.of(1)
);
assertEquals(List.of(1, 2, 3), dfsIterative(graph, 1));
}
@Test
void traversalDoesNotInventDisconnectedVertices() {
Map<Integer, List<Integer>> graph = Map.of(
1, List.of(2),
2, List.of(),
3, List.of()
);
assertEquals(List.of(1, 2), bfs(graph, 1));
}Also test an isolated start, duplicate edges, unknown start policy, directed edges, a long chain, and deterministic neighbor ordering.
Common mistakes
The first mistake is marking BFS visited only when dequeued. A diamond graph can enqueue the same vertex many times.
The second is using BFS for weighted shortest paths.
The third is assuming one source visits disconnected vertices.
The fourth is relying on recursive DFS when depth is unbounded.
The fifth is reporting one exact traversal order when neighbor order is unspecified.
The sixth is treating any visited neighbor as a cycle without considering directedness or the parent edge.
The seventh is saying O(V + E) while using an adjacency matrix.
Practical checklist
- Define directedness, weights, duplicates, and unknown vertices.
- Choose an adjacency representation.
- Use BFS for minimum-edge unweighted paths.
- Use DFS when branch completion or reachability fits.
- Mark BFS vertices when enqueued.
- Protect DFS from cycles with visited state.
- Prefer iterative DFS when depth is unbounded.
- Traverse every unvisited vertex for disconnected graphs.
- Specify neighbor ordering only if required.
- Match cycle detection to directed or undirected semantics.
- State complexity with the graph representation.
- Test cycles, self-loops, duplicates, disconnected vertices, and deep chains.
- Continue through the Algorithms learning path and topic clusters.
Frequently asked questions
Is BFS always better for shortest paths?
Only for unweighted graphs or equal-cost edges. Weighted graphs need an algorithm that accounts for costs.
Can DFS find a shortest path?
An exhaustive DFS could compare all simple paths, but ordinary DFS does not guarantee the first path is shortest and may be exponentially expensive.
Should visited be marked on push or pop?
For BFS, mark on enqueue. For iterative DFS, either can work with matching logic; marking on push limits duplicates, while marking on pop can simplify preorder templates.
Why does recursive DFS risk failure?
Every active vertex uses a Java call-stack frame. A long chain can cause StackOverflowError; an explicit ArrayDeque uses heap memory with controlled behavior.
Do trees need a visited set?
Not when the structure is guaranteed to be a tree and traversal never revisits the parent. Untrusted graph-like input should use visited protection.
Sources and further reading
- Princeton Algorithms, Undirected Graphs.
- Oracle, ArrayDeque in Java SE 25.
- Oracle, Map in Java SE 25.
Related reading
Read Queue vs Deque in Java for frontier containers, Big-O Notation Explained for O(V + E), and Heap Patterns Explained for best-first and weighted-search frontiers. Continue with the Algorithms learning path and topic clusters.