GraphsData structureaka unit-weight graph, hop graph

Unweighted Graph

A graph where every edge counts the same, so the shortest path is the one with the fewest edges and BFS finds it in O(V + E).

▶ Visualize Pattern: Breadth-First Search Practice (5)

Progress

Definition

In an unweighted graph edges have no cost, or equivalently every edge has weight 1. The distance between two vertices is the minimum number of edges on a path between them, and Breadth-First Search (BFS) computes it for all vertices from a source in O(V + E) — no heap, no relaxation.

Most interview graph problems are unweighted: grids, word ladders, social hops, state-space puzzles. Many of them never build an explicit graph at all — the neighbors of a state are generated on the fly (an implicit graph), and BFS works unchanged.

Representation is the same as any graph: Adjacency List for sparse, Adjacency Matrix for dense, or an implicit neighbors(state) function.

BFShop countlevel ordershortest pathimplicit graph

Intuition

A mental model before the formal terms.

Drop a stone in a pond. The first ripple touches everything one step away, the second ripple everything two steps away. BFS is that ripple: the first time a vertex is touched is by definition the shortest route to it, because every earlier ripple had a chance and missed.

Contrast with Weighted Graph: with unequal road lengths, the ripple metaphor breaks and you need Dijkstra's heap to decide which frontier to expand first.

How it works

BFS from source s: dist[s] = 0, queue [s]. Pop u; for each unvisited neighbor v set dist[v] = dist[u] + 1, mark visited, enqueue.
Reconstruct the path by storing parent[v] = u when v is first discovered, then walking back from the target.
For grid graphs the neighbors of (r, c) are the 4 (or 8) adjacent cells within bounds that are not blocked — no adjacency list is ever built.
Multi-source BFS: seed the queue with all sources at distance 0 to get "distance to the nearest source" for every cell (rotting oranges, walls and gates).
Bidirectional BFS from both ends halves the exponent on branching-factor-heavy searches such as Word Ladder.
For a directed unweighted graph the same BFS works following out-edges only.

Why it works

BFS processes vertices in non-decreasing order of distance: the queue always contains vertices at distance d followed by vertices at distance d + 1. Induction on d shows each vertex is first reached along a shortest path.

Because every edge has equal weight, a path with fewer edges is always shorter — so hop count and weight coincide, and Dijkstra reduces to BFS.

Operations

Operation	Description	Cost
addEdge(u, v)	Append to adjacency list(s).	O(1)
neighbors(u)	Iterate adj[u], or generate implicitly.	O(deg(u))
bfs(s)	Distances (in hops) from s to every vertex.	O(V + E)
shortestPath(s, t)	BFS with parent tracking, then walk back.	O(V + E)
multiSourceBfs(S)	Nearest-source distance for all vertices.	O(V + E)
components()	Repeated BFS/DFS.	O(V + E)

Recognition

How to tell a problem wants this.

"Minimum number of moves / steps / swaps / transformations" with no per-move cost.
The graph is a grid, a word/state space, or a set of pairs with no weights.
Shortest path where each edge is a single unit — even if the problem is phrased in terms of "distance".
Level-by-level structure: "all nodes at depth k", "nearest exit", "rotting spreads one cell per minute".

“minimum steps” → Breadth-First Search “connected groups” → Depth-First Search

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Breadth-First Search (BFS) visualization.

Graph — One edge per line: "A B". Optional "source: A" / "target: F" lines.

Queue (front → back)

1/42Start BFS from A. Put it in the queue and mark it visited with distance 0.

Current nodeIn queueVisitedBFS tree edge

PseudocodeLearn Breadth-First Search (BFS) →

1queue = [source]; visited = {source}
2while queue not empty:
3  u = queue.popleft()
4  for v in neighbors(u):
5    if v not in visited:
6      visited.add(v); parent[v] = u
7      queue.append(v)

Complexity

best O(V + E)

avg O(V + E)

worst O(V + E)

space O(V)

Speed

Pseudocode

1bfs(s): dist = [-1]*V; dist[s] = 0; q = deque([s])
2  while q: u = q.popleft()
3    for v in adj[u]: if dist[v] == -1: dist[v] = dist[u] + 1; q.append(v)
4  return dist
5grid: neighbors(r, c) = [(r+dr, c+dc) for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)) if in bounds and open]

Implementation

1import math
2from collections import deque
3 
4 
5class UnweightedGraph:
6    """Every edge costs the same, so "shortest path" means "fewest edges"
7    and BFS — not Dijkstra — is the correct and optimal tool."""
8 
91 · State: a plain adjacency list; no weights to carry
10    def __init__(self, n: int) -> None:
11        self.adj: list[list[int]] = [[] for _ in range(n)]
12 
13    def add_edge(self, u: int, v: int) -> None:
14        self.adj[u].append(v)
15        self.adj[v].append(u)
16 
17    def __len__(self) -> int:
18        return len(self.adj)
19 
202 · BFS layers: the first time a vertex is reached is via a shortest path
21    def distances_from(self, src: int) -> list[int]:
22        dist = [-1] * len(self.adj)
23        dist[src] = 0
24        q = deque([src])
25        while q:
26            u = q.popleft()
27            for v in self.adj[u]:
28                if dist[v] == -1:  # unvisited => this is the shortest way in
29                    dist[v] = dist[u] + 1
30                    q.append(v)
31        return dist
32 
333 · Recording parents turns the distance array into an actual path
34    def path_to(self, src: int, dst: int) -> list[int]:
35        parent = [-2] * len(self.adj)
36        parent[src] = -1
37        q = deque([src])
38        while q:
39            u = q.popleft()
40            if u == dst:
41                break
42            for v in self.adj[u]:
43                if parent[v] == -2:
44                    parent[v] = u
45                    q.append(v)
46        if parent[dst] == -2:
47            return []
48        path = []
49        at = dst
50        while at != -1:
51            path.append(at)
52            at = parent[at]
53        return path[::-1]
54 
554 · 0-1 BFS: weights restricted to {0, 1} still avoid a priority queue
56    def zero_one_distances(self, src: int, w: list[list[tuple[int, int]]]) -> list[float]:
57        dist: list[float] = [math.inf] * len(w)
58        dist[src] = 0
59        dq = deque([src])
60        while dq:
61            u = dq.popleft()
62            for v, cost in w[u]:
63                if dist[u] + cost < dist[v]:
64                    dist[v] = dist[u] + cost
65                    if cost == 0:
66                        dq.appendleft(v)  # free move: keep the same layer
67                    else:
68                        dq.append(v)  # costly move: next layer
69        return dist
70 
715 · Multi-source BFS: seed the queue with every source at distance 0
72    def distances_from_any(self, sources: list[int]) -> list[int]:
73        dist = [-1] * len(self.adj)
74        q: deque[int] = deque()
75        for s in sources:
76            dist[s] = 0
77            q.append(s)
78        while q:
79            u = q.popleft()
80            for v in self.adj[u]:
81                if dist[v] == -1:
82                    dist[v] = dist[u] + 1
83                    q.append(v)
84        return dist

Walkthrough

collections.deque gives O(1) popleft, append and appendleft, so both plain BFS and 0-1 BFS are linear with no tricks.
dist[v] == -1 is the combined visited flag and distance, set at enqueue time so each vertex is queued once.
path[::-1] reverses the reconstructed path with a slice, which is the idiomatic Python reverse and allocates one new list.
zero_one_distances uses appendleft for free moves and append for costly ones — the deque *is* the algorithm.
distances_from_any seeds every source before the loop, computing the distance to the nearest source in one pass.

Complexity (this implementation)

time O(V + E) for every method here · space O(V)

Unlike JavaScript, Python needs no workaround: deque.popleft is genuinely O(1), so BFS and 0-1 BFS are both linear as written.

Language notes

collections.deque is the only correct BFS queue in Python; list.pop(0) is O(n) and makes BFS quadratic.
deque([src]) seeds from an iterable, which is why the multi-source version can also be written deque(sources).
path[::-1] and reversed(path) differ: the slice returns a list, reversed returns an iterator — the former is what a list[int] return type wants.
networkx.shortest_path and scipy.sparse.csgraph.breadth_first_order are the library answers for large or labelled graphs.

Common mistakes in this language

Using a list with pop(0) instead of a deque, the direct analogue of the JavaScript shift() mistake.
Calling dq.pop(0) on a deque, which raises TypeError because deque.pop takes no argument.
Marking visited on dequeue rather than enqueue, allowing duplicates in the queue.

Language differences that matter here

Queue support decides the shape of the code: Python collections.deque and C++ std::queue/std::deque are O(1) at both ends, while JavaScript and TypeScript must use an array plus a head cursor — and even that only fixes one end, which is why the 0-1 BFS variant degrades there.
Array.prototype.shift() in JS/TS and list.pop(0) in Python are the same trap under different names: both are O(n) and both silently turn a linear BFS quadratic.
Sentinel conventions: -1 for "unvisited" works in all four, while the 0-1 variant uses INT_MAX in C++ (needing overflow care) versus Infinity/math.inf in the others, which saturate safely.
Path reversal: C++ std::reverse in place, JS/TS Array.prototype.reverse in place, Python path[::-1] producing a copy — only Python leaves the original untouched by default.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)	Vertex by id.
Search	O(deg(u))	O(V)	Edge (u, v) lookup by scanning u's list.
Insert	O(1)	O(1)	Append an edge.
Delete	O(deg(u))	O(V)	Remove an edge from u's list.
Update	O(deg(u))	O(V)	Find the edge, then change its weight.
Shortest path (BFS)	O(V + E)	O(V + E)
Multi-source BFS	O(V + E)	O(V + E)
Space	O(V + E)		Implicit graphs (grids, state spaces) need only O(V) for the visited set.

Advantages & disadvantages

Advantages

Shortest paths in linear time with a plain queue.
No weights to store; implicit graphs need no storage at all.
Level structure is explicit, which makes "distance k" and "layers" questions trivial.

Disadvantages

Cannot express differing costs; adding one weighted edge changes the algorithm class.
BFS memory is O(V) for the visited set; on huge implicit state spaces this dominates.
Hop count is a coarse metric for physical networks.

Use cases

Grid shortest paths: shortest path in a binary matrix, nearest exit, knight moves.
Word Ladder and other state-transformation puzzles.
Degrees of separation in social graphs.
Level-order traversal of trees (a tree is an unweighted graph).
Multi-source spreading: rotting oranges, walls and gates, 01-matrix.

Use it when

Every move costs the same and you need the minimum number of moves.
Grid, puzzle, or word-transformation problems.
Level/layer questions: nodes at distance k, nearest of several sources.

Avoid it when

Edges have differing costs — use a Weighted Graph with Dijkstra's Algorithm.
You need any path, not the shortest — Depth-First Search (DFS) uses less memory on deep, narrow graphs.
The state space is astronomically large with a good heuristic — consider A* Search.

Alternatives

Weighted Graph Undirected Graph Directed Graph

Common mistakes

Marking a vertex visited when it is popped instead of when it is pushed — vertices get enqueued many times and distances can be wrong.
Using DFS for shortest paths; DFS finds *a* path, not the shortest.
Using list.pop(0) in Python as a queue (O(n) per pop); use collections.deque.
Re-running BFS from every source when a single multi-source BFS suffices.
Forgetting bounds checks or blocked cells in grid neighbor generation.

Interview patterns

Shortest Path in Binary Matrix: 8-direction BFS.
Word Ladder: BFS over words, neighbors via wildcard patterns; bidirectional for speed.
Rotting Oranges: multi-source BFS, answer is the max level.
Binary Tree Level Order: BFS with level sizes.
Open the Lock / Minimum Genetic Mutation: BFS on an implicit state graph.

Interview questions on this

Choosing between BFS, DFS, Dijkstra and DPAdvanced
Stack versus queueBeginner
Recursion versus iterationIntermediate
When space complexity mattersIntermediate

Mock interviews

Course ScheduleIntermediate
Network Delay TimeAdvanced
Number of IslandsIntermediate

Interview problems

Number of Islandsmedium Binary Tree Level Order Traversalmedium Word Ladderhard Shortest Path in Binary Matrixmedium Rotting Orangesmedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related