Find if Path Exists in Graph

Q: What is the time complexity of finding if a path exists in a graph?

With BFS or DFS it is O(n + m) time and space, for n nodes and m edges: each node is visited once and each edge is checked from both ends. Union-find with union by size and path halving costs O(n + m·α(n)) time and O(n) space, where α grows so slowly that it is a small constant in practice.

Q: Why does BFS need a visited array?

Without it, a cycle like 0 → 1 → 2 → 0 sends the search around forever, and even without cycles a node with several neighbours would be queued once per neighbour. Marking each node the moment it is queued guarantees it is processed once, which is what bounds the work by O(n + m) .

Q: 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's depth grows only when its group at least doubles, which caps the depth at log n . Path compression, or the path halving used here, shortens the walk to the root every time you take it. Together they bring each operation down to α(n) .

EasyGraphs Union-find

+10

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

validPath(n: integer, edges: integer-2d-array, source: integer, destination: integer) → boolean

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 ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [u, v] with 0 ≤ u, v ≤ n-1 and u ≠ 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 → 3 uses 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 is false.

+16 hidden tests on Submit

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.

0 of 3 opened

Solution

The question is whether source and destination lie in the same connected piece of the graph. The slow way rescans the edge list until nothing new is reached. A breadth-first search over an adjacency list explores each node and edge once, and union-find gets the same answer 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

Keep a mark on every node you know you can reach, starting with source. Now read the edge list. An edge with one marked end and one unmarked end means you can reach the unmarked end too, so mark it. Repeat the whole pass until a pass marks nothing new, or destination is marked.

This is correct: a node on a path of length k from source is marked by the k-th pass at the latest, and a node is only marked when an edge leads to it from a marked node. In the first example, one pass in list order marks 1, 2 and 3 in turn, and you are done.

The cost depends on the order of the edges. If the path is listed from the far end back, each pass marks only one more node. A path through 5001 nodes then takes 5000 passes over 5000 edges, 2.5 × 10^7 edge checks, where one pass over a neighbour list would do.

Algorithm

Create reached with only source marked.
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 destination is still unmarked.
Return whether destination is 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 wastes its time rereading edges whose ends were settled long ago. Instead, list for every node the nodes it touches. Each edge [u, v] goes into both lists, because you can walk it both ways. Then explore outward from source: take a node from a queue and push each neighbour you have not seen yet.

Mark a node as seen when you push it, not when you take it out. That way no node enters the queue twice, and the search ends even when the graph has cycles, like 0 → 1 → 2 → 0. If destination ever comes out of the queue, a path exists. If the queue empties first, you have seen every node source can reach, and destination was not among them.

Every node is queued at most once and every edge is looked at twice, once from each end, so the time is O(n + m) for m edges. The neighbour lists take O(n + m) space. A queue instead of recursion keeps a 5000-node path from overflowing the call stack.

Algorithm

Build an adjacency list: for each edge [u, v], add v to u's list and u to v's list.
Mark source as seen and put it in a queue.
Take a node from the front. If it is destination, return true.
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 False

Union-find

Intuition

You do not need the path, only whether one exists. So treat the graph as groups of connected nodes. At the start every node is 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 are in the same group.

Store each group as a tree with parent links; the root names the group. find(x) walks up to the root. To merge, hang one root under the other. In the second example, [0, 1] and [0, 2] build the group {0, 1, 2} and [3, 4] builds {3, 4}; find(2) and find(4) return different roots, so the answer is false.

Two habits keep the trees flat. Hang the smaller group under the larger one, and halve the path during find by pointing each node at its grandparent. Together they make each operation cost α(n), the inverse Ackermann function, which stays below 5 for any input you will ever see. The edges are read once and only parent and size are stored: O(n) space, and no neighbour lists to build.

Algorithm

Set parent[x] = x and size[x] = 1 for every node.
For each edge [u, v], find the roots a and b of both ends.
If they differ, hang the root of the smaller group under the other and add the sizes.
Return whether find(source) equals find(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

The graph is small, but a few details decide whether the search finishes and answers right.

Adding each edge in one direction only. The graph is undirected, so [1, 0] must let you walk from 0 to 1 as well. A one-way adjacency list misses paths that use an edge backwards.
Marking nodes as seen when you take them out of the queue instead of when you put them in. A node then enters the queue once for every neighbour processed before it, so the queue can hold up to 2m entries instead of at most n.
Forgetting that source can equal destination. The answer is true even when that node has no edges at all.
Using 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] with parent[destination] in union-find. Only the roots name a group; always compare find(source) with find(destination).
Forgetting the shift in Lua and R, whose arrays start at 1: node x lives at index x+1.

Frequently asked questions4

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, reads each edge once, and shines when many connectivity questions come for the same graph, because after the merges each question costs two find calls.

What is the time complexity of finding if a path exists in a graph?

With BFS or DFS it is O(n + m) time and space, for n nodes and m edges: each node is visited once and each edge is checked from both ends. Union-find with union by size and path halving costs O(n + m·α(n)) time and O(n) space, where α grows so slowly that it is a small constant in practice.

Why does BFS need a visited array?

Without it, a cycle like 0 → 1 → 2 → 0 sends the search around forever, and even without cycles a node with several neighbours would be queued once per neighbour. Marking each node the moment it is queued guarantees it is processed once, which is what bounds the work by O(n + m).

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's depth grows only when its group at least doubles, which caps the depth at log n. Path compression, or the path halving used here, shortens the walk to the root every time you take it. Together they bring each operation down to α(n).

Python

def validPath(n, edges, source, destination):
    # Write code here

Test cases

Case 1

Case 2

Input

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

Expected

true

Find if Path Exists in Graph

Function

Constraints

Examples

Hints

Solution

Sweep the edges until nothing changes

Breadth-first search

Union-find

Pitfalls and edge cases

Frequently asked questions4

Similar problems