Find if Path Exists in Graph: BFS, DFS, and Union-Find

You are given a bidirectional graph with n nodes labeled 0 to n - 1. You are also given a list of edges, where each edge connects two nodes. Given a source node and a destination node, determine whether there is a valid path from source to destination.

This is LeetCode 1971: Find if Path Exists in Graph, and it is one of the cleanest introductions to graph connectivity. The problem boils down to a single question: are two nodes in the same connected component?

Why this problem matters

Graph connectivity is one of the most fundamental concepts in computer science. Can you get from point A to point B? That question appears in social networks (are two users connected?), road networks (is there a route between two cities?), and dependency graphs (can this module reach that module?).

This problem strips away all the complexity and gives you the purest version of the question. No weights, no directions, no shortest path. Just "does a path exist?" It is the perfect starting point for learning BFS, DFS, and Union-Find, because you can focus entirely on the traversal mechanics without worrying about optimization.

Once you have this pattern down, you can layer on top of it: shortest path (BFS on unweighted graphs), cycle detection, topological sort, and more. But it all starts here.

The key insight

If we can reach the destination from the source by traversing edges, a path exists. We do not need to find the actual path or its length. We just need to know whether the two nodes are connected.

This means any graph traversal that starts at source and explores reachable nodes will work. If we ever visit destination, return True. If we exhaust all reachable nodes without finding it, return False.

There are three natural approaches:

1. BFS: explore layer by layer from the source. If destination appears in any layer, return True.
2. DFS: dive deep from the source, backtracking when stuck. If any path reaches destination, return True.
3. Union-Find: process all edges to group connected nodes, then check if source and destination share the same root.

The BFS/DFS solution

from collections import deque

def valid_path(n: int, edges: list[list[int]], source: int, destination: int) -> bool:
    if source == destination:
        return True

    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = set([source])
    queue = deque([source])

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor == destination:
                return True
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return False

Let's walk through this.

First, we handle the trivial case: if source == destination, the answer is always True. No traversal needed.

Next, we build an adjacency list from the edge list. Since the graph is bidirectional, each edge [u, v] adds v to u's neighbor list and u to v's neighbor list. This takes O(E) time and O(N + E) space.

Then we run BFS. We start with the source in the queue and in the visited set. For each node we dequeue, we check its neighbors. If any neighbor is the destination, we return True immediately. If a neighbor has not been visited, we mark it visited and add it to the queue. If the queue empties without finding the destination, we return False.

The DFS version follows the same logic with a stack (or recursion) instead of a queue. Both traverse the same set of nodes; they just visit them in a different order.

Visual walkthrough

Let's trace BFS through a 6-node graph. Source is node 0, destination is node 3. Watch how BFS explores outward layer by layer until it finds the destination.

The key moment is Step 5. When BFS dequeues node 2 and checks its neighbors, it finds node 3, the destination. At that point we can return True immediately without processing the rest of the queue. BFS guarantees that we find the destination as soon as it becomes reachable from the explored frontier.

The Union-Find solution

def valid_path(n: int, edges: list[list[int]], source: int, destination: int) -> bool:
    parent = list(range(n))
    rank = [0] * n

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a: int, b: int) -> None:
        ra, rb = find(a), find(b)
        if ra == rb:
            return
        if rank[ra] < rank[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        if rank[ra] == rank[rb]:
            rank[ra] += 1

    for u, v in edges:
        union(u, v)

    return find(source) == find(destination)

Union-Find takes a completely different approach. Instead of traversing the graph, we process every edge and merge the two endpoints into the same set. After processing all edges, we simply check whether source and destination share the same root. If they do, they are in the same connected component and a path exists.

The find function uses path compression (each node points directly to its grandparent on every lookup, gradually flattening the tree). The union function uses union by rank to keep trees balanced. Together, these optimizations make each operation nearly O(1), specifically O(alpha(N)) where alpha is the inverse Ackermann function.

Union-Find shines when you need to answer many connectivity queries on the same graph, because the preprocessing is done once and each query is nearly constant time. For a single query like this problem, BFS and Union-Find perform similarly.

Complexity analysis

N is the number of nodes, E is the number of edges, and alpha(N) is the inverse Ackermann function (effectively constant for all practical input sizes).

BFS/DFS Time: Building the adjacency list takes O(E). The traversal visits each node at most once and processes each edge at most once. Total: O(N + E).

BFS/DFS Space: The adjacency list takes O(N + E). The visited set and queue each take O(N). Total: O(N + E).

Union-Find Time: Initializing the parent array takes O(N). Processing each edge with union takes O(alpha(N)). The final find query is O(alpha(N)). Total: O(N + E * alpha(N)), which is effectively O(N + E).

Union-Find Space: The parent and rank arrays each take O(N). No adjacency list is needed. Total: O(N).

Edge cases

• Source equals destination: always return True. No traversal needed, and this is easy to forget.
• No edges: each node is its own isolated component. Return True only if source == destination.
• Single edge: the graph has just two connected nodes. Check if they match source and destination.
• Disconnected graph: the graph has multiple components. Source and destination might be in different components. BFS from source will never reach destination, so it returns False.
• Large linear chain: nodes form a single long path 0-1-2-...-n. BFS/DFS will traverse the entire chain. Watch for recursion depth limits if using recursive DFS.

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently:

1. BFS/DFS graph traversal with a visited set

The core pattern of exploring all reachable nodes from a starting point:

visited = set([start])
queue = deque([start])

while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

This is the same traversal you use in Number of Islands (flood fill on a grid) and Clone Graph (traversal with parallel construction). The only difference is what you do when you visit a node. Here, you check if it is the destination. In other problems, you count components, compute distances, or build copies.

2. Union-Find with path compression and union by rank

The pattern for efficiently grouping elements into disjoint sets:

parent = list(range(n))
rank = [0] * n

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return
    if rank[ra] < rank[rb]:
        ra, rb = rb, ra
    parent[rb] = ra
    if rank[ra] == rank[rb]:
        rank[ra] += 1

Union-Find appears in Number of Provinces (counting connected components), Kruskal's minimum spanning tree, and any problem where you need to dynamically merge sets and query membership. The find with path compression and union by rank together guarantee nearly constant time per operation.

Common mistakes

1. Forgetting to handle source == destination. If source and destination are the same node, the answer is True regardless of edges. Some implementations fail this case because they only check neighbors, never the starting node itself.

2. Building a directed adjacency list for an undirected graph. Each edge [u, v] must add both graph[u].append(v) and graph[v].append(u). If you only add one direction, BFS will miss half the connections.

3. Marking nodes visited at dequeue time instead of enqueue time. This causes duplicate entries in the queue. It does not produce wrong answers, but it wastes memory and time, potentially causing TLE on large inputs.

4. Using recursive DFS on very large graphs. Python's default recursion limit is 1,000. For graphs with long chains, recursive DFS will hit a RecursionError. Use iterative DFS (with an explicit stack) or BFS instead.

5. Skipping path compression in Union-Find. Without path compression, find degrades to O(N) per call, making the overall solution O(N * E) in the worst case. Always flatten the tree during find operations.

From understanding to recall

You have seen three ways to check graph connectivity: BFS, DFS, and Union-Find. The logic is clear. Build an adjacency list, traverse from source, check if destination is reachable. Or union all edges and compare roots. Simple enough.

But can you write it from scratch in under 5 minutes? The details matter. Adding both directions for undirected edges. Marking visited at enqueue time. Path compression in the find function. Union by rank. These are small things that become automatic with practice, but trip you up if you have not drilled them recently.

Spaced repetition locks these details in. You write the BFS traversal loop and the Union-Find skeleton from memory at increasing intervals. After a few rounds, you do not think about the mechanics. You just write them.

Related posts

• Number of Islands - Grid-based graph traversal using DFS/BFS flood fill
• Course Schedule - Graph connectivity and cycle detection with DFS
• Number of Provinces - Union-Find for connected components

CodeBricks breaks Find if Path Exists in Graph into its BFS-traversal and Union-Find building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a graph connectivity problem shows up in your interview, you do not think about it. You just write it.