Traversal, connected components, shortest path — DFS and BFS applied to graphs.
Published September 21, 2026
A graph is a set of nodes (vertices) connected by edges: cities and roads, users and friendships, web pages and links, cells of a grid and their neighbours. Almost every graph algorithm starts from one of two ways of exploring it:
Both visit every reachable node in O(V + E) time (V nodes, E edges). The difference is the order, and that order decides which problems each one solves naturally.
// Adjacency list: for each node, the list of its neighbours — the default choice
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]); // omit this line for a DIRECTED graph
}
boolean[n][n]): O(V²) memory, but an O(1) "is there an edge?" check. Only sensible for small or dense graphs.boolean[] visited = new boolean[n];
void dfs(int u) {
visited[u] = true;
for (int v : adj.get(u)) {
if (!visited[v]) dfs(v);
}
}
The visited check is essential. Without it, any cycle (even A–B–A in an undirected graph) loops forever. Recursive DFS can overflow Java's stack on very deep graphs (for example a path of 100,000 nodes). An explicit Deque used as a stack avoids that.
DFS is the natural fit when you need to explore complete paths or structure: connected components, cycle detection, topological order, path existence, and backtracking over choices.
Every DFS started from an unvisited node discovers one whole component, so counting DFS starts counts components. Grids work the same way, with cells as nodes:
public int numIslands(char[][] grid) {
int islands = 0;
for (int r = 0; r < grid.length; r++)
for (int c = 0; c < grid[0].length; c++)
if (grid[r][c] == '1') { sink(grid, r, c); islands++; }
return islands;
}
private void sink(char[][] g, int r, int c) {
if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;
g[r][c] = '0'; // mark visited by overwriting (mutates input)
sink(g, r + 1, c); sink(g, r - 1, c); sink(g, r, c + 1); sink(g, r, c - 1);
}
Overwriting cells saves a separate visited array, but modifies the input. Say so in an interview, and use a boolean[][] if the input must stay intact.
int[] bfsDistances(int start) {
int[] dist = new int[n];
Arrays.fill(dist, -1); // -1 = not reached
Deque<Integer> queue = new ArrayDeque<>();
dist[start] = 0;
queue.add(start);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : adj.get(u)) {
if (dist[v] == -1) { // mark when ENQUEUED, not when dequeued
dist[v] = dist[u] + 1;
queue.add(v);
}
}
}
return dist;
}
Key property: BFS reaches nodes in order of their distance (number of edges) from the start. So in an unweighted graph, the first time BFS reaches a node is along a shortest path. Mark nodes as visited when you enqueue them. Marking on dequeue lets the same node be enqueued many times.
BFS is the natural fit when the question is about fewest steps: shortest path in unweighted graphs, minimum moves, nearest target, or anything by level.
Start from all sources at once by putting them all in the queue at distance 0. Each cell's distance is then its distance to the nearest source:
Sometimes the node isn't just a position. In "shortest path in a grid with at most k obstacle removals", the state is (row, col, removalsLeft). BFS over states, with a visited set on the full state, works the same way. Only the definition of a node changes.
| Question | Choose | Why |
|---|---|---|
| Fewest edges/steps from A to B (unweighted) | BFS | Explores in order of distance |
| Nearest X from many starting points | Multi-source BFS | One pass for all sources |
| Count or label connected components | Either | Both visit a whole component |
| Cycle detection in a directed graph | DFS | Needs "currently on the path" state |
| Topological order | DFS or Kahn's BFS | See Topological Sort |
| Enumerate all paths or configurations | DFS / backtracking | Explores one full path at a time |
| Is the graph bipartite (2-colourable)? | Either | Colour alternately, and a conflict means no |
| Shortest path with weights | Dijkstra (or 0-1 BFS with a deque for weights 0/1) | Plain BFS ignores weights |
boolean isBipartite(List<List<Integer>> adj) {
int[] colour = new int[adj.size()]; // 0 = uncoloured, 1 / -1 = two sides
for (int s = 0; s < adj.size(); s++) {
if (colour[s] != 0) continue;
Deque<Integer> q = new ArrayDeque<>(List.of(s));
colour[s] = 1;
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj.get(u)) {
if (colour[v] == colour[u]) return false; // neighbours on the same side
if (colour[v] == 0) { colour[v] = -colour[u]; q.add(v); }
}
}
}
return true;
}
The outer loop matters: graphs can be disconnected, and each component must be checked. Forgetting to start from every unvisited node is a common bug in all graph problems.
Q: Why does BFS give the shortest path in an unweighted graph but not a weighted one? A: BFS processes nodes in order of the number of edges from the start, so the first arrival uses the fewest edges. With weights, a path with more edges can be cheaper, so you need Dijkstra's algorithm (a priority queue ordered by total distance), or 0-1 BFS when weights are only 0 and 1.
Q: What's the time and space complexity of DFS and BFS? A: Both are O(V + E) time with an adjacency list: each node is processed once and each edge examined once (twice for undirected graphs). Space is O(V) for the visited set, plus the recursion stack (DFS) or the queue (BFS). The queue can hold a whole level, and the stack a whole path.
Q: When would you prefer iterative DFS over recursive? A: When the graph can be very deep (long chains, large grids): recursion depth equals path length, and Java's default stack can overflow at tens of thousands of frames. An explicit stack has no such limit.
Q: How do you reconstruct the actual shortest path, not just its length?
A: Record a parent[v] = u whenever BFS first reaches v from u. After reaching the target, follow parents back to the start and reverse the list.
Q: Why mark visited when enqueuing in BFS? A: If you mark on dequeue, a node can be added to the queue many times, once from each neighbour that sees it before it's processed. That wastes time and memory, and on dense graphs can blow up the queue. Marking on enqueue guarantees each node enters the queue exactly once.