SyntaxPilot
Courses/DSA and Coding Problems/Lesson 47
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 47 of 90

Graphs: representation, BFS and DFS

queued

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 0 to n-1 so 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 a is linked to b, then b is linked to a.
  • 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: t is reachable from s if some path goes from s to t.
  • 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: V is the number of vertices, E the 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] is true when a and b are 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: ArrayDeque with add (to the back) and poll (from the front).
  • Stack: last in, first out (LIFO), like a pile of plates. In Java: ArrayDeque with push (on top) and pop (from the top).
  • Visited / seen array: a boolean[] (or BFS's dist[] with -1 meaning "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:

  1. dist[] = -1 everywhere (-1 means "not visited yet").
  2. dist[s] = 0; put s in the queue.
  3. Take v from the front; if v == t, return dist[v].
  4. For each neighbour w with dist[w] == -1: dist[w] = dist[v] + 1, and add w to the back. (Mark it right away, when it joins the queue.)
  5. Queue empty: t was 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

  1. 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).

  1. 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.

  1. 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).

  1. Clone Graph (LeetCode 133): given one node of a connected undirected graph (each Node has a val and a list of neighbors), 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

  1. 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.
  2. 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.
  3. Does DFS give the shortest path? No. It finds some path; it can wander far before reaching a nearby target.
  4. 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).
  5. 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).
  6. Recursive or iterative DFS? Recursive is shorter, but a deep graph (a 1 lakh line) overflows Java's call stack with StackOverflowError; an explicit ArrayDeque stack does not.
  7. How do you return the route itself? Store parent[w] = v when w is discovered, then follow parents back from the target and reverse.
  8. 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.