Find if Path Exists in Graph: BFS on an Adjacency List
Solve Find if Path Exists in Graph by building an adjacency list and running BFS with a visited set — intuition, JavaScript code, a walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
You're handed a bag of undirected edges and two node numbers. The only question: can you get from one to the other by walking along edges? No shortest path, no route to print — just yes or no. This is the "are these two nodes in the same connected component?" question, and it's the gateway to every graph traversal problem that follows.
The trap is that the input arrives as an edge list — a flat array of pairs — which is useless for traversal. You can't ask "what are node 3's neighbors?" without scanning the whole list. The entire solution is two moves: reshape the edges into an adjacency list, then flood outward from the source until you either touch the destination or run out of nodes.
The problem
Given an integer n (nodes are labeled 0 to n-1), a list of undirected edges where edges[i] = [u, v] connects u and v, plus a source and a destination, return true if a path exists from source to destination, and false otherwise.
Input: n = 6
edges = [[0,1],[0,2],[1,3],[2,3],[3,4],[4,5]]
source = 0, destination = 5
Output: true // 0 → 1 → 3 → 4 → 5 is one valid pathInput: n = 6
edges = [[0,1],[0,2],[3,5],[5,4],[4,3]]
source = 0, destination = 5
Output: false // {0,1,2} and {3,4,5} are separate componentsTwo things shape the solution: edges are undirected (so [u, v] lets you walk both ways), and you only need existence, so the moment you reach destination you can stop and return true.
The brute force baseline
The naive instinct is to treat the raw edge list as your graph. From the source, scan every edge to find one that touches a node you've reached, mark the other endpoint reached, and repeat until nothing changes.
function validPath(n, edges, source, destination) {
const reached = new Set([source]);
let changed = true;
while (changed) {
changed = false;
for (const [u, v] of edges) {
if (reached.has(u) && !reached.has(v)) { reached.add(v); changed = true; }
if (reached.has(v) && !reached.has(u)) { reached.add(u); changed = true; }
}
}
return reached.has(destination);
}It works, but it rescans all the edges on every pass, and it can take up to n passes to propagate reachability across a long chain. That's O(n · m) where m is the edge count — on a graph with 2×10⁵ edges and nodes, that's tens of billions of operations. The waste is structural: you keep re-reading edges that have nothing to do with the frontier you're expanding.
The key insight: reshape, then flood
Two ideas fix both problems.
First, build an adjacency list. Walk the edges once and, for each [x, y], record y as a neighbor of x and x as a neighbor of y (both directions, because the graph is undirected). Now map[curr] answers "who are curr's neighbors?" in O(1) instead of an O(m) scan.
Second, run BFS from the source. Keep a queue of nodes to process and a visited set so no node is ever enqueued twice. Pull a node off the front, check if it's the destination, and if not, push all its unvisited neighbors. Because you mark each node visited the instant you enqueue it, every node enters the queue at most once — the flood expands outward, never backtracking, never looping, even when the graph has cycles.
The visited set is what makes this terminate. Without it, a cycle like 3 → 1 → 3 would spin forever.
The optimal solution
var validPath = function(n, edges, source, destination) {
let map = {};
for (let [x, y] of edges) {
if (!map[x]) map[x] = [];
if (!map[y]) map[y] = [];
map[x].push(y);
map[y].push(x);
}
let q = [source];
let visited = new Set();
visited.add(source);
while (q.length) {
let curr = q.shift();
if (curr === destination) {
return true;
}
for (let neighbor of map[curr]) {
if (!visited.has(neighbor)) {
q.push(neighbor);
visited.add(neighbor);
}
}
}
return false;
};The ordering inside the loop matters: mark a neighbor visited at enqueue time, not when you later dequeue it. If you waited until dequeue, the same node could get pushed by two different neighbors before either processes it, and the queue would balloon. Marking on enqueue caps the queue at n entries total.
This also handles the source === destination case for free: the first thing the loop does after dequeuing source is compare it to destination, so a zero-length "path" returns true immediately.
Walkthrough
Trace the connected example: n = 6, edges = [[0,1],[0,2],[1,3],[2,3],[3,4],[4,5]], source = 0, destination = 5.
After the build loop, the adjacency list is:
0 → [1, 2] 1 → [0, 3] 2 → [0, 3]
3 → [1, 2, 4] 4 → [3, 5] 5 → [4]BFS then runs, starting with q = [0] and visited = {0}:
| Step | Dequeue curr | Unvisited neighbors pushed | Queue after | Visited |
|---|---|---|---|---|
| 1 | 0 | 1, 2 | [1, 2] | {0, 1, 2} |
| 2 | 1 | 3 (0 skipped) | [2, 3] | {0, 1, 2, 3} |
| 3 | 2 | none (0, 3 seen) | [3] | {0, 1, 2, 3} |
| 4 | 3 | 4 (1, 2 skipped) | [4] | {0, 1, 2, 3, 4} |
| 5 | 4 | 5 (3 skipped) | [5] | {0,1,2,3,4,5} |
| 6 | 5 | — curr === destination | — | — |
Step 6 is the payoff: 5 comes off the front of the queue, matches destination, and the function returns true. Notice that node 2 in step 3 contributed nothing — both its neighbors were already visited — which is exactly the redundant work the visited set silently absorbs. In the disconnected example, the queue would instead drain to empty after visiting only {0, 1, 2}, and the function falls through to return false.
Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(n + m) | build list touches each of m edges once; BFS visits each node once and scans each edge's two endpoints |
| Space | O(n + m) | adjacency list stores 2m entries; queue and visited set hold up to n nodes |
Here n is the node count and m is the edge count. Every node is enqueued at most once and every edge is examined a constant number of times, so the traversal is linear in the size of the graph — a decisive win over the O(n · m) baseline.
Common mistakes
- Marking visited on dequeue instead of enqueue. This lets a node get pushed multiple times before it's processed, inflating the queue and, in dense graphs, degrading performance badly. Mark it the moment you enqueue.
- Forgetting the reverse edge. The graph is undirected. If you only push
yontomap[x]and skipmap[y].push(x), you build a directed graph and will miss valid backward paths. - No visited set at all. Any cycle turns BFS into an infinite loop. The set is not an optimization — it's what guarantees termination.
- Skipping the
source === destinationcheck. When source equals destination the answer istruewith a zero-length path. The loop's first comparison covers it; don't special-case it wrong by returningfalse. - Assuming the input is connected. A disconnected graph is the whole point of the "no path" case — let BFS drain naturally and return
false.
Where this pattern shows up next
Adjacency-list + BFS/DFS traversal is the spine of graph problems. Once this clicks, these are the natural next steps:
- Max Area of Island — the same flood-fill traversal, but counting the size of each connected component on a grid.
- All Paths From Source to Target — when you need every route, not just whether one exists, DFS with backtracking takes over.
- Redundant Connection — the union-find alternative to traversal, built for exactly this connectivity question.
- Course Schedule II — directed graphs plus cycle detection, where traversal order becomes a topological sort.
You can also step through the traversal interactively and watch the queue fill and drain, node by node, across BFS, iterative DFS, and recursive DFS.
FAQ
Should I use BFS or DFS for this problem?
Either works, and both are O(n + m). Since you only care whether a path exists — not the shortest one — the choice is a wash. BFS uses an explicit queue and floods level by level; DFS uses a stack (or recursion) and dives deep first. DFS can be marginally lighter on a long, thin graph because the queue in BFS may hold a whole "level" of nodes at once. The interactive visualizer lets you flip between iterative DFS, BFS, and recursive DFS on the same input to compare.
Why build an adjacency list instead of searching the edge list directly?
The edge list is a flat array of pairs, so finding a node's neighbors means scanning every edge — O(m) per lookup. During a traversal you do that lookup once per node, turning the whole search into O(n · m). Converting to an adjacency list is a one-time O(m) cost that makes every subsequent neighbor lookup O(1), which is what collapses the total work down to linear time.
What does the visited set actually prevent?
It prevents two failures. First, infinite loops: an undirected edge [3, 1] means 3 is a neighbor of 1 and vice versa, so without a visited set BFS would bounce between them forever, and any cycle would never terminate. Second, redundant work: a node reachable by several paths would otherwise be enqueued and processed multiple times. Marking a node visited the instant it's enqueued guarantees each node is handled exactly once.
How would I solve this with union-find instead?
Union-find (disjoint set union) groups connected nodes without any traversal. You initialize each node as its own set, then union the two endpoints of every edge. After processing all edges, source and destination are connected exactly when they share the same root — a single find(source) === find(destination) check. With path compression and union by rank it runs in near-linear time and shines when you'd otherwise re-run connectivity checks repeatedly. Redundant Connection is the classic problem where union-find is the intended tool.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.