DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Find if Path Exists in Graph

easyGraphs

Problem statement

There are n nodes labelled 0 to n - 1 and a list edges, where each [a, b] is a two-way link between node a and node b. No link connects a node to itself and no link appears twice.

Given a source node and a destination node, return true if you can walk from source to destination by following links, and false otherwise.

Examples

Example 1

Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]], source = 0, destination = 2

Output: true

Explanation: Walk 0 -> 1 -> 2.

Example 2

Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]], source = 1, destination = 4

Output: false

Explanation: Nodes 3 and 4 form their own group with no link to 0, 1 or 2.

Hints

Approach

Build an adjacency list once, then run a breadth-first search from source, stopping as soon as destination comes off the queue.

  1. For each edge [a, b], add b to a's neighbour list and a to b's.
  2. Put source in a queue and mark it seen.
  3. Pop a node. If it is destination, return true. Otherwise push every unseen neighbour and mark it seen.
  4. If the queue empties, the two nodes are in different groups.

Every node and every edge is handled a constant number of times, so this is strictly linear. It also exits early, which union-find cannot do because it must read every edge first. A depth-first search with an explicit stack works identically.

ComplexityTime O(V + E)Space O(V + E)
Python
from collections import deque
class Solution:
def validPath(self, n: int, edges: list[list[int]], source: int, destination: int) -> bool:
graph = [[] for _ in range(n)]
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
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]:
seen[nxt] = True
queue.append(nxt)
return False

Follow-up questions

  • Return the actual path, not just true/false. (Store each node's parent during BFS and walk back from destination.)
  • Links are added one at a time and you must answer connectivity queries between additions. Which approach still works?

Frequently asked questions

Return true. All three solutions handle it: the brute force marks source reached before the loop, union-find compares a root with itself, and BFS pops source first.

It is the simplest form of a reachability question: can host A reach host B through a set of network links, can one VPC route to another through peering connections, or does a service sit anywhere in another service's dependency chain. Being able to explain when to reach for BFS versus union-find is the real test.

BFS is the default for a single question on a fixed graph. Union-find is the better fit when links keep arriving and you must answer "are these connected yet?" after each one, because it never rebuilds anything.