Find if Path Exists in Graph
An undirected graph has n nodes, numbered 0 to n-1. Each entry [u, v] of edges connects nodes u and v, and you can walk an edge in either direction. Return true if you can walk from source to destination along the edges, and false otherwise. A node can always reach itself.
Function
- ninteger
- the number of nodes
- edgesinteger-2d-array
- the edges, each a pair [u, v] of connected nodes
- sourceinteger
- the node you start from
- destinationinteger
- the node you want to reach
- Returnsboolean
- whether some path joins source and destination
Constraints
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [u, v]with0 ≤ u, v ≤ n-1andu ≠ v- No edge appears twice, in either direction.
0 ≤ source, destination ≤ n-1
Examples
- Input
- n = 6edges = [[0, 1], [1, 2], [2, 3], [4, 5]]source = 0destination = 3
- Output
- true
- Explanation
- The walk
0 → 1 → 2 → 3uses three edges, so node 3 is reachable. Nodes 4 and 5 form a separate piece that the walk never needs.
- Input
- n = 5edges = [[0, 1], [0, 2], [3, 4]]source = 2destination = 4
- Output
- false
- Explanation
- From node 2 you reach 0 and then 1, and nothing else. Node 4 only touches node 3, and no edge links
{0, 1, 2}to{3, 4}, so the answer isfalse.
Follow-up
Suppose the edges are one-way: [u, v] lets you walk from u to v only. Which of the three approaches still work, and what do you change in them?
Hints
Open them one at a time. Each one gives away a little more.
Forget the destination for a moment. Which nodes can you reach from
sourceat all?Grow the set of reached nodes from
source, one edge at a time, and stop when it stops growing. A search over a neighbour list does that in one pass, as long as you never visit a node twice.Either run a BFS from
sourcewith aseenarray, or merge the two ends of every edge into one group with union-find and check whethersourceanddestinationend up with the same root.
Solution
The question is whether source and destination lie in the same connected piece of the graph. A breadth-first search over an adjacency list answers it by exploring each node and edge once. Union-find answers it by merging groups as it reads the edges, with no neighbour lists at all.
Sweep the edges until nothing changes
Correct, but does not finish on the largest tests
Intuition
Mark source as reached and pass over the edge list. An edge with one marked end lets you reach the other end, so mark it. Repeat until a pass marks nothing new or destination is marked.
A node at distance k from source is marked by pass k at the latest, and a node is marked only through an edge from a marked node, so the answer is right. The cost depends on the edge order. If a path is listed from the far end back, each pass marks one node: a path of 5000 edges takes 5000 passes, 2.5 × 10^7 edge checks.
Algorithm
- Create
reachedwith onlysourcemarked. - Pass over every edge
[u, v]. If exactly one end is marked, mark the other and record that something changed. - Repeat the pass while something changed and
destinationis still unmarked. - Return whether
destinationis marked.
def validPath(n, edges, source, destination):
reached = [False] * n
reached[source] = True
changed = True
while changed and not reached[destination]:
changed = False
for u, v in edges:
# An edge with exactly one reached end pulls the other end in.
if reached[u] != reached[v]:
reached[u] = reached[v] = True
changed = True
return reached[destination]Breadth-first search
Intuition
The sweep rereads edges whose ends were settled long ago. Instead, list for every node the nodes it touches, putting each edge in both lists because you can walk it both ways. Then explore outward from source with a queue, pushing each neighbour you have not seen yet.
Mark a node as seen when you push it. Then no node enters the queue twice, and the search ends even on a cycle like 0 → 1 → 2 → 0. If the queue empties before destination comes out, you have seen every node source can reach. Each node is queued once and each edge is checked from both ends: O(n + m) time and space for m edges.
Algorithm
- Build an adjacency list: for each edge
[u, v], addvtou's list andutov's list. - Mark
sourceas seen and put it in a queue. - Take a node from the front. If it is
destination, returntrue. - Mark and enqueue each neighbour that is not seen yet.
- When the queue is empty, return
false.
from collections import deque
def validPath(n, edges, source, destination):
# Each edge goes both ways, so list it under both of its ends.
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
seen = [False] * n
seen[source] = True
queue = deque([source])
while queue:
node = queue.popleft()
if node == destination:
return True
for nxt in graph[node]:
if not seen[nxt]:
# Mark on push, so no node enters the queue twice.
seen[nxt] = True
queue.append(nxt)
return FalseUnion-find
Intuition
You need to know whether a path exists, not what it is. Start with every node in a group of its own. An edge [u, v] says u and v belong together, so merge their groups. After all edges, source and destination are connected exactly when they share a group.
Store each group as a tree of parent links; the root names the group, and find(x) walks up to it. In the second example, [0, 1] and [0, 2] build {0, 1, 2} and [3, 4] builds {3, 4}, so find(2) and find(4) return different roots.
Hanging the smaller tree under the larger, and pointing each node at its grandparent during find, keep the trees flat. Each operation then costs α(n), the inverse Ackermann function, which stays below 5 for any real input. Only parent and size are stored: O(n) space.
Algorithm
- Set
parent[x] = xandsize[x] = 1for every node. - For each edge
[u, v], find the rootsaandbof both ends. - If they differ, hang the root of the smaller group under the other and add the sizes.
- Return whether
find(source)equalsfind(destination).
def validPath(n, edges, source, destination):
parent = list(range(n)) # every node starts as its own group
size = [1] * n
def find(x):
# Walk up to the group's root, halving the path on the way.
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
a, b = find(u), find(v)
if a != b:
# Hang the smaller group under the larger one.
if size[a] < size[b]:
a, b = b, a
parent[b] = a
size[a] += size[b]
return find(source) == find(destination)
Pitfalls and edge cases
- Adding each edge in one direction only. With
edges = [[1, 0]], a one-way list finds no path from 0 to 1. - Marking a node as seen when you take it out of the queue. It then enters the queue once for every neighbour processed before it, up to
2mentries instead ofn. - Missing that
sourcecan equaldestination. The answer istrueeven when that node has no edges. - Recursive DFS on a long path. A path through 5000 nodes is 5000 nested calls, past Python's default limit of 1000. Use a queue or an explicit stack.
- Comparing
parent[source]withparent[destination]in union-find. Only the roots name a group, so comparefind(source)withfind(destination).
Frequently asked questions3
Should I use BFS, DFS or union-find to check if a path exists?
All three are linear or close to it. BFS and DFS can stop as soon as they meet the destination, and they can return the path itself. Union-find needs no adjacency list and suits many connectivity questions on one graph: after the merges, each question costs two find calls.
What is the time complexity of finding if a path exists in a graph?
BFS or DFS takes O(n + m) time and space for n nodes and m edges. Union-find with union by size and path halving takes O(n + m·α(n)) time and O(n) space, and α(n) is a small constant in practice.
What do path compression and union by size do in union-find?
They keep the trees shallow so find stays fast. Union by size hangs the smaller tree under the larger, so a node gets deeper only when its group at least doubles, which caps the depth at log n. Path compression, or path halving, shortens the walk to the root every time find runs.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def validPath(n, edges, source, destination):
# Write code hereTest #1
Test #2
Arguments
n = 6 edges = [[0, 1], [1, 2], [2, 3], [4, 5]] source = 0 destination = 3
Expected Output
true