These are the notes for DSA episode 47, the first episode of the graphs chapter. Metro maps, road networks, friends on social media and links between web pages are all graphs. Today we learn to store a graph in code (an adjacency matrix, which crashes for real on a big city, and the adjacency list, which does not), and to explore it in the two classic ways: BFS (breadth-first search), which gives the fewest stops between two stations, and DFS (depth-first search), which answers "is there any path at all?" (LeetCode 1971). We start from a real-life problem (a metro app that must show the fewest stops), solve it the obvious way (try every path), watch it hit Time Limit Exceeded on just 49 stations, and finish with O(V + E) solutions that handle 90,000 stations in milliseconds. Every program below was run with javac 21 with an 8-second limit (like the SyntaxPilot compiler), and every output shown is real.
The problem, in real life
Think of a city metro: stations joined by tracks. You want to go from home to college with the fewest stops. But the lines cross each other and loop back, so there are many possible routes. A metro app still answers instantly, even for a network with a lakh (100,000) stops. Today we invent how.
| On the metro | In code |
|---|---|
| A station | a vertex (also called a node), numbered 0 … n-1 |
| A track between two stations | an edge, a pair {a, b} |
| A track that runs both ways | an undirected edge |
| A one-way street | a directed edge |
| Stations one track away | the neighbours of a vertex |
| A route | a path |
| The number of stops on a route | the length of the path (its number of edges) |
| The app's "fewest stops" answer | BFS (breadth-first search) |
| "Can I get there at all?" | DFS or BFS: does any path exist? |
Our tiny metro for the whole episode has six stations, 0 to 5, and five tracks:
1
/ \
0 3 —— 4 5 (station 5 has no tracks)
\ /
2
Input: n = 6, tracks = {{0,1}, {0,2}, {1,3}, {2,3}, {3,4}}.
Every word, from zero
- Graph: a set of vertices plus the edges between them. Nothing more.
- Vertex (node): one "thing" in the graph: a station, a person, a web page. We number them
0ton-1so they can be array indexes. - Edge: a link between two vertices: a track, a friendship, a hyperlink. Given as a pair
{a, b}. - Undirected edge: works both ways, like a metro track: if
ais linked tob, thenbis linked toa. - Directed edge: works one way only, like a one-way street or "A follows B" on social media.
- Neighbour: the neighbours of a vertex are the vertices exactly one edge away. Station 3's neighbours are 1, 2 and 4. Station 5 has no neighbours, so it cannot be reached from anywhere.
- Path: a walk along edges from one vertex to another. Its length is the number of edges on it, which is the number of stops. 0 → 1 → 3 → 4 has length 3.
- Simple path: a path that never visits the same vertex twice (no loops).
- Reachable:
tis reachable fromsif some path goes fromstot. - Connected component (group): a set of vertices that can all reach each other, and nothing outside it. Our metro has two:
{0, 1, 2, 3, 4}and{5}. - V and E:
Vis the number of vertices,Ethe number of edges. Our metro: V = 6, E = 5. Costs of graph algorithms are written with them, like O(V + E). - Adjacent: "next to each other", that is, joined by an edge.
- Adjacency matrix: a V × V table of
true/false; cell[a][b]istruewhenaandbare adjacent. - Adjacency list: for each vertex, a list of just its neighbours. In Java:
List<List<Integer>>. - Sparse graph: a graph with few edges compared with V × V (a metro: each station has 2-4 tracks). Most real graphs are sparse.
- BFS (breadth-first search): explore the graph in rings, by distance from the start: everything 1 step away, then 2 steps, then 3. "Breadth" means width: go wide before you go deep. Uses a queue.
- DFS (depth-first search): go as deep as you can along one route, and only back up when stuck, like following one corridor of a maze to its end. Uses a stack (your own, or the call stack in a recursive version).
- Queue: first in, first out (FIFO), like a ticket-counter line. In Java:
ArrayDequewithadd(to the back) andpoll(from the front). - Stack: last in, first out (LIFO), like a pile of plates. In Java:
ArrayDequewithpush(on top) andpop(from the top). - Visited / seen array: a
boolean[](or BFS'sdist[]with-1meaning "not yet") that remembers which vertices were already reached, so each one is processed only once and we never go round in circles. - Call stack: the memory where Java keeps one frame for every method call that has not returned yet. Too many nested calls overflow it:
StackOverflowError.
Problem statements
Problem 1: fewest stops from s to t
Given n stations, a list of undirected tracks, a start s and a target t, return the fewest stops (edges) on a path from s to t, or -1 if t cannot be reached.
| Call (on our metro) | Answer | Why |
|---|---|---|
fewest(adj, 0, 4) |
3 |
0 → 1 → 3 → 4 (0 → 2 → 3 → 4 is also 3) |
fewest(adj, 0, 0) |
0 |
you are already there |
fewest(adj, 0, 5) |
-1 |
station 5 has no tracks |
Constraints (a real city): 1 ≤ n ≤ 10^5, up to 2 × 10^5 tracks, 0 ≤ s, t < n, tracks are undirected.
Problem 2: Find if Path Exists in Graph (LeetCode 1971, Easy)
Given n vertices 0 … n-1, an array edges of undirected edges, a source and a destination, return true if there is a valid path from source to destination, else false.
| Input | Output |
|---|---|
n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2 |
true |
n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5 |
false |
Constraints: 1 ≤ n ≤ 2 × 10^5, 0 ≤ edges.length ≤ 2 × 10^5, no duplicate edges, no edge from a vertex to itself.
Storing a graph
Problems usually hand you n and a list of edges. Before exploring, you turn that list into something where "who are the neighbours of v?" is fast.
Way 1: an adjacency matrix
An n × n table: m[a][b] = true if a and b are linked. For an undirected track, set both m[a][b] and m[b][a]. "Are a and b linked?" is one lookup, O(1). But it needs n × n cells, even though each station has only a few tracks.
import java.util.*;
public class Main {
public static void main(String[] args) {
int n = 6;
int[][] tracks = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}};
boolean[][] m = new boolean[n][n];
for (int[] e : tracks) { m[e[0]][e[1]] = true; m[e[1]][e[0]] = true; }
System.out.println("0-1 linked? " + m[0][1] + ", 0-4 linked? " + m[0][4]);
boolean[][] city = new boolean[100000][100000];
System.out.println("built");
}
}
Real output:
0-1 linked? true, 0-4 linked? false
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at Main.main(Main.java:10)
The small matrix works. The real city does not: a lakh × a lakh is 10^10 cells (a thousand crore). A Java boolean in an array takes 1 byte, so that is about 10 gigabytes, for a city that has maybe two lakh tracks. "built" is never printed. Matrix space is O(V²).
Way 2: an adjacency list
For each vertex, keep a list of just its neighbours. In Java, a list of lists of integers: adj.get(3) is [1, 2, 4]. For an undirected edge, add it twice: b into a's list and a into b's list.
import java.util.*;
public class Main {
static List<List<Integer>> build(int n, int[][] edges) {
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]);
}
return adj;
}
public static void main(String[] args) {
int[][] tracks = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}};
List<List<Integer>> adj = build(6, tracks);
for (int v = 0; v < 6; v++) System.out.println(v + " -> " + adj.get(v));
}
}
Real output:
0 -> [1, 2]
1 -> [0, 3]
2 -> [0, 3]
3 -> [1, 2, 4]
4 -> [3]
5 -> []
Exactly our map: station 5 has an empty list. Space is O(V + E): one list per vertex, plus two entries per edge, only for tracks that really exist. This is what almost every graph problem uses, and build is reused by every program below.
| Adjacency matrix | Adjacency list | |
|---|---|---|
| Space | O(V²) | O(V + E) |
| "Are a and b linked?" | O(1) | O(degree of a) |
| "List the neighbours of v" | O(V) (scan a whole row) | O(degree of v) |
| 1 lakh stations | OutOfMemoryError |
a few MB |
| Good for | small, dense graphs (V up to a few thousand) | almost everything else |
(The degree of a vertex is its number of neighbours.)
Brute force: try every path
The obvious way: start at s, try every simple path, and keep the shortest one that reaches t. To avoid going round in circles, never step onto a station that is already on the current path (on[]), and take each station off again on the way back, so other paths may use it. This is a recursive DFS over all simple paths, with backtracking (undoing a choice when you return).
import java.util.*;
public class Main {
static List<List<Integer>> build(int n, int[][] edges) {
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]);
}
return adj;
}
static int best;
static void paths(List<List<Integer>> adj, int v, int t, int stops, boolean[] on) {
if (v == t) { best = Math.min(best, stops); return; }
on[v] = true;
for (int w : adj.get(v))
if (!on[w]) paths(adj, w, t, stops + 1, on);
on[v] = false;
}
static int fewest(List<List<Integer>> adj, int s, int t) {
best = Integer.MAX_VALUE;
paths(adj, s, t, 0, new boolean[adj.size()]);
return best == Integer.MAX_VALUE ? -1 : best;
}
public static void main(String[] args) {
int[][] tracks = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}};
List<List<Integer>> adj = build(6, tracks);
System.out.println(fewest(adj, 0, 4) + " " + fewest(adj, 0, 0) + " " + fewest(adj, 0, 5));
}
}
Real output:
3 0 -1
Correct on all three questions.
A 7 × 7 grid of stations: Time Limit Exceeded
Now a small city laid out as a grid: 7 × 7 = 49 stations, with a track between every pair of side-by-side stations, and we ask from one corner (station 0) to the opposite corner (station 48). Replace main with:
public static void main(String[] args) {
int k = 7, n = k * k;
List<int[]> e = new ArrayList<>();
for (int r = 0; r < k; r++)
for (int c = 0; c < k; c++) {
if (c + 1 < k) e.add(new int[]{r * k + c, r * k + c + 1});
if (r + 1 < k) e.add(new int[]{r * k + c, (r + 1) * k + c});
}
List<List<Integer>> adj = build(n, e.toArray(new int[0][]));
long t0 = System.nanoTime();
int d = fewest(adj, 0, n - 1);
System.out.println(n + " stations: " + d + " stops, " + (System.nanoTime() - t0) / 1000000 + " ms");
}
Station (r, c) (row r, column c) gets the number r * k + c; each station is linked to its right and lower neighbour. Real result: Time Limit Exceeded, nothing printed (stopped after 8 s in the SyntaxPilot compiler; our run was still going when timeout 10 killed it). Only 49 stations!
Why trying every path is slow
- The number of simple paths explodes as the map grows. On a 7 × 7 grid there are 575,780,564 (about 57 crore) different simple paths from one corner to the other (a known count, OEIS A007764), and the brute force walks every one of them, many with dozens of steps.
- Each extra row and column multiplies that number again: the time is exponential.
- But to know the fewest stops we never need the long, winding paths at all. The brute force also re-visits the same station again and again, once for every path that passes through it.
The key insight: explore in rings (BFS)
Drop a stone into a pond. The first ripple starts where it falls (distance 0). The ripples spread one ring at a time: everything 1 step away, then 2, then 3. The first ripple to reach a boat got there the shortest way.
So: explore the nearest stations first, and the first time we reach a station, we already know its fewest stops, so we never need to visit it again. This is breadth-first search (BFS). To serve stations in order of distance, keep the stations still to explore in a queue (first in, first out).
BFS from station 0 on our metro:
| Step | Take from the queue | New neighbours get | Queue after | dist[] (0..5) |
|---|---|---|---|---|
| start | 0 gets 0 | [0] | 0 -1 -1 -1 -1 -1 | |
| 1 | 0 | 1 and 2 get 1 | [1, 2] | 0 1 1 -1 -1 -1 |
| 2 | 1 | 3 gets 2 | [2, 3] | 0 1 1 2 -1 -1 |
| 3 | 2 | (3 already has a distance: skip) | [3] | 0 1 1 2 -1 -1 |
| 4 | 3 | 4 gets 3 | [4] | 0 1 1 2 3 -1 |
| 5 | 4 = target | return 3 |
Ring 0 is {0}, ring 1 is {1, 2}, ring 2 is {3}, ring 3 is {4}. The skip in step 3 is what keeps every station to one visit.
BFS in five steps:
dist[]= -1 everywhere (-1 means "not visited yet").dist[s] = 0; putsin the queue.- Take
vfrom the front; ifv == t, returndist[v]. - For each neighbour
wwithdist[w] == -1:dist[w] = dist[v] + 1, and addwto the back. (Mark it right away, when it joins the queue.) - Queue empty:
twas never reached, return -1.
The optimal solution in Java: BFS
import java.util.*;
public class Main {
static List<List<Integer>> build(int n, int[][] edges) {
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]);
}
return adj;
}
static int fewest(List<List<Integer>> adj, int s, int t) {
int[] dist = new int[adj.size()];
Arrays.fill(dist, -1);
Deque<Integer> q = new ArrayDeque<>();
dist[s] = 0; q.add(s);
while (!q.isEmpty()) {
int v = q.poll();
if (v == t) return dist[v];
for (int w : adj.get(v))
if (dist[w] == -1) { dist[w] = dist[v] + 1; q.add(w); }
}
return -1;
}
public static void main(String[] args) {
int[][] tracks = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}};
List<List<Integer>> adj = build(6, tracks);
System.out.println(fewest(adj, 0, 4) + " " + fewest(adj, 0, 0) + " " + fewest(adj, 0, 5));
}
}
Real output:
3 0 -1
The same answers as the brute force, including both edge cases (s == t gives 0, an unreachable target gives -1), with each station visited once. ArrayDeque is Java's fast double-ended queue; add puts at the back and poll takes from the front.
The grid that timed out, and a much bigger one
With the BFS fewest and the grid main from above:
| Grid | Real output |
|---|---|
7 × 7 (int k = 7) |
49 stations: 12 stops, 0 ms |
300 × 300 (int k = 300) |
90000 stations: 598 stops, 113 ms |
598 = 299 steps down + 299 steps across. Ninety thousand stations in about a tenth of a second, where the brute force could not finish 49.
DFS: is there any path? (LeetCode 1971)
Sometimes we only need to know whether a path exists. Then the other classic works too: depth-first search (DFS). Go as deep as you can along one route, and only back up when you are stuck, like walking a maze and following one corridor to its end before trying the next.
In code it is the same loop as BFS, with a stack instead of a queue: the vertex added last is explored first. We use our own stack (an ArrayDeque with push / pop) instead of recursion, so a very deep graph cannot overflow Java's call stack (see bug 3).
Warning: DFS finds a path, but not necessarily the shortest one. For the fewest stops, use BFS.
import java.util.*;
public class Main {
static List<List<Integer>> build(int n, int[][] edges) {
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]);
}
return adj;
}
static boolean validPath(int n, int[][] edges, int s, int t) {
List<List<Integer>> adj = build(n, edges);
boolean[] seen = new boolean[n];
Deque<Integer> stack = new ArrayDeque<>();
stack.push(s); seen[s] = true;
while (!stack.isEmpty()) {
int v = stack.pop();
if (v == t) return true;
for (int w : adj.get(v))
if (!seen[w]) { seen[w] = true; stack.push(w); }
}
return false;
}
public static void main(String[] args) {
System.out.println(validPath(3, new int[][]{{0, 1}, {1, 2}, {2, 0}}, 0, 2));
System.out.println(validPath(6, new int[][]{{0, 1}, {0, 2}, {3, 5}, {5, 4}, {4, 3}}, 0, 5));
System.out.println(validPath(1, new int[][]{}, 0, 0));
int n = 100000;
int[][] line = new int[n - 1][];
for (int i = 0; i + 1 < n; i++) line[i] = new int[]{i, i + 1};
System.out.println(validPath(n, line, 0, n - 1));
}
}
Real output:
true
false
true
true
true: the triangle links 0 and 2.false: 0's group{0, 1, 2}and 5's group{3, 4, 5}never touch.true: a single vertex reaches itself.true: a line of a lakh stations, 0 – 1 – 2 – … – 99999, end to end, with no stack overflow.
The same solution in C++
BFS: fewest stops
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> build(int n, const vector<pair<int, int>>& edges) {
vector<vector<int>> adj(n);
for (auto [a, b] : edges) {
adj[a].push_back(b);
adj[b].push_back(a);
}
return adj;
}
int fewest(const vector<vector<int>>& adj, int s, int t) {
vector<int> dist(adj.size(), -1);
queue<int> q;
dist[s] = 0; q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
if (v == t) return dist[v];
for (int w : adj[v])
if (dist[w] == -1) { dist[w] = dist[v] + 1; q.push(w); }
}
return -1;
}
int main() {
vector<pair<int, int>> tracks = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}};
auto adj = build(6, tracks);
cout << fewest(adj, 0, 4) << " " << fewest(adj, 0, 0) << " " << fewest(adj, 0, 5) << "\n";
}
The adjacency list is a vector<vector<int>>; queue<int> needs front() then pop() (C++'s pop returns nothing). Real output (g++ -O2 -std=c++17):
3 0 -1
DFS: Find if Path Exists
#include <bits/stdc++.h>
using namespace std;
bool validPath(int n, const vector<pair<int, int>>& edges, int s, int t) {
vector<vector<int>> adj(n);
for (auto [a, b] : edges) { adj[a].push_back(b); adj[b].push_back(a); }
vector<bool> seen(n, false);
stack<int> st;
st.push(s); seen[s] = true;
while (!st.empty()) {
int v = st.top(); st.pop();
if (v == t) return true;
for (int w : adj[v])
if (!seen[w]) { seen[w] = true; st.push(w); }
}
return false;
}
int main() {
cout << boolalpha;
cout << validPath(3, {{0, 1}, {1, 2}, {2, 0}}, 0, 2) << "\n";
cout << validPath(6, {{0, 1}, {0, 2}, {3, 5}, {5, 4}, {4, 3}}, 0, 5) << "\n";
cout << validPath(1, {}, 0, 0) << "\n";
int n = 100000;
vector<pair<int, int>> line;
for (int i = 0; i + 1 < n; i++) line.push_back({i, i + 1});
cout << validPath(n, line, 0, n - 1) << "\n";
}
boolalpha prints true/false instead of 1/0. Real output:
true
false
true
true
The same solution in Python
BFS: fewest stops
from collections import deque
def build(n, edges):
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
return adj
def fewest(adj, s, t):
dist = [-1] * len(adj)
q = deque([s])
dist[s] = 0
while q:
v = q.popleft()
if v == t:
return dist[v]
for w in adj[v]:
if dist[w] == -1:
dist[w] = dist[v] + 1
q.append(w)
return -1
tracks = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
adj = build(6, tracks)
print(fewest(adj, 0, 4), fewest(adj, 0, 0), fewest(adj, 0, 5))
Use collections.deque with popleft(): list.pop(0) would shift the whole list every time, O(n) per pop. Real output:
3 0 -1
DFS: Find if Path Exists
def valid_path(n, edges, s, t):
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
seen = [False] * n
stack = [s]
seen[s] = True
while stack:
v = stack.pop()
if v == t:
return True
for w in adj[v]:
if not seen[w]:
seen[w] = True
stack.append(w)
return False
print(valid_path(3, [(0, 1), (1, 2), (2, 0)], 0, 2))
print(valid_path(6, [(0, 1), (0, 2), (3, 5), (5, 4), (4, 3)], 0, 5))
print(valid_path(1, [], 0, 0))
n = 100000
print(valid_path(n, [(i, i + 1) for i in range(n - 1)], 0, n - 1))
A plain Python list is a fine stack (append / pop at the end are O(1)). The explicit stack matters even more in Python: its default recursion limit is only 1,000 calls. Real output:
True
False
True
True
Three real bugs
Bug 1: adding each track only one way
for (int[] e : edges) {
adj.get(e[0]).add(e[1]); // the reverse edge adj.get(e[1]).add(e[0]) is missing
}
// main: fewest(adj, 4, 0) with the BFS
Real output: -1. Every track now points only from the smaller station towards 4 (0 → 1, 0 → 2, 1 → 3, 2 → 3, 3 → 4), so from station 4 there is no way back. In an undirected graph each edge goes into both lists.
Bug 2: recursive DFS with no seen array
static boolean dfs(List<List<Integer>> adj, int v, int t, boolean[] seen) {
if (v == t) return true;
for (int w : adj.get(v))
if (dfs(adj, w, t, seen)) return true;
return false;
}
public static void main(String[] args) {
List<List<Integer>> adj = build(3, new int[][]{{0, 1}});
System.out.println(dfs(adj, 0, 2, new boolean[3]));
}
Stations 0 and 1 are linked, and we look for station 2 (which is unreachable). Real output:
Exception in thread "main" java.lang.StackOverflowError
at Main.dfs(Main.java:15)
at Main.dfs(Main.java:16)
0 calls 1, 1 calls 0, 0 calls 1 again, forever, until the call stack runs out. Even a single undirected edge is a loop of length 2. Fix: mark seen[v] = true and only call dfs on neighbours with !seen[w].
Bug 3: correct recursive DFS on a 1 lakh long line
static boolean dfs(List<List<Integer>> adj, int v, int t, boolean[] seen) {
if (v == t) return true;
seen[v] = true;
for (int w : adj.get(v))
if (!seen[w] && dfs(adj, w, t, seen)) return true;
return false;
}
public static void main(String[] args) {
int n = 100000;
int[][] line = new int[n - 1][];
for (int i = 0; i + 1 < n; i++) line[i] = new int[]{i, i + 1};
List<List<Integer>> adj = build(n, line);
System.out.println(dfs(adj, 0, n - 1, new boolean[n]));
}
This DFS is correct now. Real output:
Exception in thread "main" java.lang.StackOverflowError
at Main.dfs(Main.java:16)
at Main.dfs(Main.java:17)
Every station on the line is one more nested call, and Java's default call stack cannot hold a lakh of them. On deep graphs use your own stack (an ArrayDeque), like validPath above, which printed true for this exact line.
One more: marking a station when it leaves the queue
The narration warns: in BFS, mark a station when it joins the queue, not when it leaves. We ran the "wrong" version (a done[] array set only after poll, skipping stations already done) on the 300 × 300 grid. Real output: 90000 stations: 598 stops, 179401 queue adds. The answer is still right, but stations were added to the queue about twice each (once per edge reaching them, 179,401 adds for 90,000 stations), which wastes time and memory. Marking on join (the BFS above) adds each station at most once.
Complexity
| Approach | Time | Space | 7 × 7 grid | 300 × 300 grid |
|---|---|---|---|---|
| Adjacency matrix (storage) | build O(V²) | O(V²) | 1 lakh stations: OutOfMemoryError |
|
| Try every path | exponential (57 crore paths on 7 × 7) | O(V) recursion | TLE | |
| BFS (adjacency list) | O(V + E) | O(V + E) list, O(V) dist + queue | 0 ms | 113 ms |
| Iterative DFS (adjacency list) | O(V + E) | O(V + E) list, O(V) seen + stack | 1 lakh line: fine |
Why O(V + E): each vertex enters the queue (or stack) at most once, and each undirected edge is looked at twice, once from each end.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
boolean[100000][100000] |
java.lang.OutOfMemoryError: Java heap space |
n × n cells (about 10 GB) | an adjacency list |
| Edge added one way in an undirected graph | -1 for 4 → 0 |
undirected = both ways | add a → b and b → a |
DFS without seen |
java.lang.StackOverflowError |
goes round a loop forever | mark each vertex seen |
| Recursion on a 1 lakh long line | java.lang.StackOverflowError |
too many nested calls | an explicit stack (ArrayDeque) |
| Trying every path for the fewest stops | Time Limit Exceeded at 49 stations | the number of paths explodes | BFS |
| Marking in BFS when a vertex leaves the queue | 179,401 queue adds for 90,000 stations | a vertex can be added once per edge | mark (dist[w] = …) when it joins |
| Using DFS for the fewest stops | a path that is not the shortest | DFS goes deep, not in rings | BFS for unweighted shortest paths |
Python BFS with list.pop(0) |
slow on big graphs | each pop shifts the list, O(n) | collections.deque and popleft() |
Mini project: the metro route planner
Build a small console app for a real-looking metro. Give stations names ("Home", "Market", "College", …) and map each name to a number with a HashMap<String, Integer>. Read tracks as pairs of names, build the adjacency list, and for a query "from A to B" print the fewest stops and the actual route (practice 1: keep a parent[]). Then add: (a) "unreachable" when BFS returns -1, (b) the number of separate groups of stations (practice 2), and (c) one-way tracks for a line under repair (a directed edge: add it to one list only, on purpose this time).
Practice
- Print the route, not just the stops.
Solution
In BFS, remember each station's parent: the station it was first reached from. Then walk back from t to s through the parents and reverse.
import java.util.*;
public class Main {
static List<List<Integer>> build(int n, int[][] edges) {
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]);
}
return adj;
}
static List<Integer> route(List<List<Integer>> adj, int s, int t) {
int[] parent = new int[adj.size()];
Arrays.fill(parent, -2); // -2 = not visited yet
Deque<Integer> q = new ArrayDeque<>();
parent[s] = -1; q.add(s); // -1 = the start has no parent
while (!q.isEmpty()) {
int v = q.poll();
if (v == t) break;
for (int w : adj.get(v))
if (parent[w] == -2) { parent[w] = v; q.add(w); }
}
List<Integer> path = new ArrayList<>();
if (parent[t] == -2) return path; // unreachable: empty route
for (int v = t; v != -1; v = parent[v]) path.add(v);
Collections.reverse(path);
return path;
}
public static void main(String[] args) {
int[][] tracks = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}};
List<List<Integer>> adj = build(6, tracks);
System.out.println(route(adj, 0, 4));
System.out.println(route(adj, 0, 0));
System.out.println(route(adj, 0, 5));
}
}
Real output:
[0, 1, 3, 4]
[0]
[]
The route has 4 stations, so 3 stops, matching fewest. Still O(V + E).
- Count the groups of linked stations (connected components).
Solution
Go through every station; each time you find one not yet seen, that is a new group: count it and run a DFS from it to mark its whole group.
import java.util.*;
public class Main {
static List<List<Integer>> build(int n, int[][] edges) {
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]);
}
return adj;
}
static int countGroups(int n, int[][] edges) {
List<List<Integer>> adj = build(n, edges);
boolean[] seen = new boolean[n];
int groups = 0;
for (int start = 0; start < n; start++) {
if (seen[start]) continue;
groups++; // a new, untouched group
Deque<Integer> stack = new ArrayDeque<>();
stack.push(start); seen[start] = true;
while (!stack.isEmpty()) {
int v = stack.pop();
for (int w : adj.get(v))
if (!seen[w]) { seen[w] = true; stack.push(w); }
}
}
return groups;
}
public static void main(String[] args) {
System.out.println(countGroups(6, new int[][]{{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}}));
System.out.println(countGroups(6, new int[][]{{0, 1}, {0, 2}, {3, 5}, {5, 4}, {4, 3}}));
System.out.println(countGroups(5, new int[][]{}));
}
}
Real output:
2
2
5
Our metro: {0..4} and {5}. LeetCode's second example: {0, 1, 2} and {3, 4, 5}. Five stations with no tracks: five groups. Every vertex and edge is still handled once: O(V + E). Next episode's "number of islands" is this same idea on a map.
- Find if Path Exists (LeetCode 1971) with BFS instead.
Solution
Change the stack into a queue: add + poll instead of push + pop. Everything else stays.
import java.util.*;
public class Main {
static boolean validPath(int n, int[][] edges, int s, int t) {
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]); }
boolean[] seen = new boolean[n];
Deque<Integer> q = new ArrayDeque<>();
q.add(s); seen[s] = true;
while (!q.isEmpty()) {
int v = q.poll(); // poll = take from the FRONT (queue)
if (v == t) return true;
for (int w : adj.get(v))
if (!seen[w]) { seen[w] = true; q.add(w); }
}
return false;
}
public static void main(String[] args) {
System.out.println(validPath(3, new int[][]{{0, 1}, {1, 2}, {2, 0}}, 0, 2));
System.out.println(validPath(6, new int[][]{{0, 1}, {0, 2}, {3, 5}, {5, 4}, {4, 3}}, 0, 5));
System.out.println(validPath(1, new int[][]{}, 0, 0));
int n = 100000;
int[][] line = new int[n - 1][];
for (int i = 0; i + 1 < n; i++) line[i] = new int[]{i, i + 1};
System.out.println(validPath(n, line, 0, n - 1));
}
}
Real output:
true
false
true
true
For "does a path exist?" BFS and DFS are equally good: both O(V + E).
- Clone Graph (LeetCode 133): given one node of a connected undirected graph (each
Nodehas avaland a list ofneighbors), return a deep copy: brand-new nodes linked the same way.
Solution
BFS over the original graph with a HashMap from each original node to its copy. The map doubles as the visited set: a node is copied (and queued) the first time it is seen, and every edge is copied when its owner is taken from the queue.
import java.util.*;
public class Main {
static class Node {
int val;
List<Node> neighbors = new ArrayList<>();
Node(int val) { this.val = val; }
}
static Node cloneGraph(Node node) {
if (node == null) return null;
Map<Node, Node> copy = new HashMap<>(); // original -> its clone (also our "visited")
Deque<Node> q = new ArrayDeque<>();
copy.put(node, new Node(node.val)); q.add(node);
while (!q.isEmpty()) {
Node v = q.poll();
for (Node w : v.neighbors) {
if (!copy.containsKey(w)) { copy.put(w, new Node(w.val)); q.add(w); }
copy.get(v).neighbors.add(copy.get(w));
}
}
return copy.get(node);
}
public static void main(String[] args) {
// LeetCode 133 example: adjList = [[2,4],[1,3],[2,4],[1,3]]
Node[] g = new Node[5];
for (int i = 1; i <= 4; i++) g[i] = new Node(i);
int[][] adj = {{}, {2, 4}, {1, 3}, {2, 4}, {1, 3}};
for (int i = 1; i <= 4; i++) for (int j : adj[i]) g[i].neighbors.add(g[j]);
Node c = cloneGraph(g[1]);
Map<Integer, Node> byVal = new TreeMap<>();
Deque<Node> q = new ArrayDeque<>();
q.add(c); byVal.put(c.val, c);
while (!q.isEmpty()) {
Node v = q.poll();
for (Node w : v.neighbors) if (!byVal.containsKey(w.val)) { byVal.put(w.val, w); q.add(w); }
}
for (Node v : byVal.values()) {
List<Integer> ns = new ArrayList<>();
for (Node w : v.neighbors) ns.add(w.val);
System.out.println(v.val + " -> " + ns + (v == g[v.val] ? " (same object!)" : " (new object)"));
}
}
}
Real output:
1 -> [2, 4] (new object)
2 -> [1, 3] (new object)
3 -> [2, 4] (new object)
4 -> [1, 3] (new object)
The copy has the same shape, and every node is a new object (== compares object identity). O(V + E) time and O(V) extra space.
Quick quiz
Edges: 0-1, 1-2, 2-5, 0-3, 3-4, 4-5 (undirected). What does BFS return for fewest(adj, 0, 5): 3, 2, 4 or -1?
Answer
3. Both routes, 0 → 1 → 2 → 5 and 0 → 3 → 4 → 5, take three stops. Ring 1 is {1, 3}, ring 2 is {2, 4}, and 5 is in ring 3. Running the BFS program above with these edges really prints 3.
Interview questions
- Adjacency matrix or adjacency list? A list for almost everything: O(V + E) space. A matrix only for small, dense graphs or when you need O(1) "are a and b linked?" checks.
- Why does BFS give the shortest path in an unweighted graph? The queue serves vertices in order of distance (ring by ring), so the first time a vertex is reached, it is by a path with the fewest edges.
- Does DFS give the shortest path? No. It finds some path; it can wander far before reaching a nearby target.
- What is the time complexity of BFS and DFS, and why? O(V + E): each vertex is pushed at most once, and each edge is examined a constant number of times (twice when undirected).
- Why mark a vertex when it is added, not when it is removed? Otherwise it can be added once per incoming edge (we measured 179,401 adds for 90,000 stations).
- Recursive or iterative DFS? Recursive is shorter, but a deep graph (a 1 lakh line) overflows Java's call stack with
StackOverflowError; an explicitArrayDequestack does not. - How do you return the route itself? Store
parent[w] = vwhenwis discovered, then follow parents back from the target and reverse. - What if the tracks had different lengths (minutes)? Then the graph is weighted, and plain BFS no longer gives the shortest time; that needs Dijkstra's algorithm (a later episode).
Glossary
| Term | Meaning |
|---|---|
| Graph | A set of vertices plus the edges between them |
| Vertex (node) | One item in a graph (a station), numbered 0 … n-1 |
| Edge | A link between two vertices (a track), given as a pair {a, b} |
| Undirected edge | Works both ways: a–b means b–a |
| Directed edge | Works one way only (a one-way street) |
| Neighbour | A vertex exactly one edge away |
| Adjacent | Joined by an edge |
| Degree | The number of neighbours of a vertex |
| Path | A walk along edges; its length is its number of edges (stops) |
| Simple path | A path that never repeats a vertex |
| Reachable | There is a path from s to t |
| Connected component (group) | A set of vertices that all reach each other and nothing else |
| V, E | The number of vertices, the number of edges |
| Sparse graph | A graph with far fewer than V² edges |
| Adjacency matrix | A V × V true/false table of which pairs are linked; O(V²) space |
| Adjacency list | For each vertex, a list of its neighbours; O(V + E) space |
List<List<Integer>> |
Java's usual adjacency list type |
| Brute force | Trying every possibility (here: every simple path) |
| Backtracking | Undoing a choice when a recursive call returns (on[v] = false) |
| Exponential time | Time that multiplies with every step of growth in the input |
| BFS (breadth-first search) | Explore in rings by distance, with a queue; gives the fewest edges |
| DFS (depth-first search) | Go as deep as possible, then back up, with a stack |
| Queue (FIFO) | First in, first out; ArrayDeque.add / poll |
| Stack (LIFO) | Last in, first out; ArrayDeque.push / pop |
ArrayDeque |
Java's fast double-ended queue, used as a queue or a stack |
dist[] |
BFS's distance array; -1 means not visited yet |
| Visited / seen array | Remembers which vertices were already reached |
parent[] |
The vertex each vertex was first reached from; rebuilds the route |
| Call stack | Memory holding one frame per unfinished method call |
StackOverflowError |
Java's error when the call stack runs out (too deep or infinite recursion) |
OutOfMemoryError: Java heap space |
Java's error when an object (here a giant matrix) does not fit in memory |
| Deep copy | A copy made of brand-new objects, linked the same way as the original |
| Weighted graph | A graph whose edges have lengths or costs |
| O(V + E) | Time or space proportional to the vertices plus the edges |
| Time Limit Exceeded (TLE) | The program was stopped for running too long (8 s in the SyntaxPilot compiler) |
| Lakh, crore | 1 lakh = 100,000; 1 crore = 10,000,000 |
Summary
- A graph is vertices plus edges; edges are undirected (both ways) or directed (one way). A path's length is its number of edges.
- Store graphs as an adjacency list, O(V + E). A matrix needs V² cells: 1 lakh stations is a real
OutOfMemoryError. - Trying every path is exponential: Time Limit Exceeded at only 49 stations (57 crore paths).
- BFS: a queue and a
dist[]array; explore in rings; the first visit is the fewest stops. 90,000 stations in 113 ms. - DFS: the same loop with a stack; answers "is there any path?" (LeetCode 1971), but not the shortest one.
- Mark vertices as visited (when they join), add undirected edges both ways, and use your own stack on deep graphs. Both searches are O(V + E).
Next episode: Number of islands: a map of land and water is a graph in disguise, and today's BFS and DFS solve it.