LeetCode 1971 - Find if Path Exists in Graph

LeetCode Problem 1971

Difficulty: 🟢 Easy
Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory

Solution

Problem Understanding

The problem asks us to determine whether a path exists between two nodes in an undirected graph. The graph is defined by n vertices labeled from 0 to n - 1 and a list of edges, where each edge connects two distinct vertices. The key points are that the graph is bi-directional, there are no duplicate edges, and no self-loops. The input source and destination are vertex indices, and the output should be a boolean indicating whether there exists a sequence of edges connecting the source to the destination.

The constraints tell us the graph can be quite large: up to 200,000 vertices and 200,000 edges. This means any approach that has more than linear or near-linear time complexity in the number of vertices and edges is likely too slow. The graph may also be disconnected, so simply checking neighbors of a single vertex is not sufficient. Important edge cases include when source equals destination, when the graph has isolated vertices, or when edges is empty.

Approaches

A brute-force approach is to perform a complete search of the graph using either Depth-First Search (DFS) or Breadth-First Search (BFS). Starting from the source vertex, we would recursively or iteratively explore every neighbor, marking visited vertices to avoid cycles, until we either reach the destination or exhaust all reachable nodes. While correct, this approach will have a time complexity of O(V + E) which is acceptable here, but a naive recursive DFS may hit Python's recursion limit for very large graphs, making an iterative approach safer.

A more sophisticated approach is to use a Union-Find (Disjoint Set Union) data structure. The insight is that two nodes are connected if they belong to the same connected component. We can iterate through all edges, union the nodes, and finally check if source and destination share the same root. This approach is also O(V + E) in practice but has the advantage of simpler iterative operations without risk of recursion depth errors.

Approach	Time Complexity	Space Complexity	Notes
DFS/BFS	O(V + E)	O(V)	Explores reachable nodes; iterative DFS or BFS avoids recursion limits
Union-Find	O(E * α(V))	O(V)	Union-Find with path compression and union by rank efficiently groups connected components

Algorithm Walkthrough

We will use the BFS approach as the optimal solution for clarity and robustness in Python and Go.

1. Build the adjacency list: Iterate through the list of edges, adding each edge to both vertices’ neighbor lists. This allows O(1) access to neighbors for exploration.
2. Initialize the BFS: Create a queue initialized with the source vertex and a visited set to track visited nodes.
3. Iterative BFS loop: While the queue is not empty, dequeue the front node. If this node is the destination, return true.
4. Explore neighbors: For each neighbor of the current node, if it has not been visited, mark it as visited and enqueue it.
5. Return result: If the queue empties without finding the destination, return false.

Why it works: BFS explores all vertices reachable from the source in increasing order of distance. If the destination is reachable, BFS will encounter it; otherwise, all reachable vertices will be exhausted.

Python Solution

from collections import deque
from typing import List

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        if source == destination:
            return True

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

        # BFS initialization
        visited = [False] * n
        queue = deque([source])
        visited[source] = True

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

        return False

The implementation starts by handling the edge case where the source equals the destination. The adjacency list allows efficient neighbor lookup. BFS ensures all reachable nodes are visited exactly once, and the visited array prevents cycles.

Go Solution

package main

func validPath(n int, edges [][]int, source int, destination int) bool {
    if source == destination {
        return true
    }

    // Build adjacency list
    graph := make([][]int, n)
    for _, edge := range edges {
        u, v := edge[0], edge[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }

    // BFS initialization
    visited := make([]bool, n)
    queue := []int{source}
    visited[source] = true

    // BFS loop
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        if node == destination {
            return true
        }
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }

    return false
}

The Go implementation mirrors Python, using slices for adjacency lists and the queue. There are no concerns with recursion depth in BFS.

Worked Examples

Example 1: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2

Step	Queue	Visited	Action
1	[0]	[0]	Start BFS at 0
2	[1, 2]	[0,1,2]	Explore neighbors 1 and 2
3	1	[0,1,2]	Node 1 visited; neighbors already visited
4	2	[0,1,2]	Node 2 is destination; return True

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

Step	Queue	Visited	Action
1	[0]	[0]	Start BFS at 0
2	[1,2]	[0,1,2]	Explore neighbors of 0
3	[2]	[0,1,2]	Visit 1, no new neighbors
4	[]	[0,1,2]	Visit 2, no new neighbors; queue empty
5	[]	[0,1,2]	Destination not reached; return False

Complexity Analysis

Measure	Complexity	Explanation
Time	O(V + E)	BFS visits each vertex once and iterates through all edges
Space	O(V + E)	Adjacency list O(E), visited array O(V), queue up to O(V)

The complexity is linear in the size of the graph, which is optimal for large sparse graphs.

Test Cases

# Basic examples
assert Solution().validPath(3, [[0,1],[1,2],[2,0]], 0, 2) == True  # cycle
assert Solution().validPath(6, [[0,1],[0,2],[3,5],[5,4],[4,3]], 0, 5) == False  # disconnected

# Edge cases
assert Solution().validPath(1, [], 0, 0) == True  # single node
assert Solution().validPath(2, [], 0, 1) == False  # two nodes, no edges
assert Solution().validPath(4, [[0,1],[1,2],[2,3]], 0, 3) == True  # linear path
assert Solution().validPath(4, [[0,1],[1,2]], 0, 3) == False  # linear path, destination disconnected

Test	Why
Cycle graph	Validates multiple paths
Disconnected graph	Checks BFS does not cross components
Single node	Edge case with trivial path
Two nodes, no edges	Edge case with no path possible
Linear connected	Confirms BFS finds path along chain
Linear disconnected	Confirms BFS correctly identifies unreachable nodes

Edge Cases

The first edge case is when source equals destination. A naive BFS might still enqueue and explore neighbors unnecessarily, but our implementation handles this immediately by returning True.

The second edge case is an empty edge list. The graph may consist of isolated vertices, and BFS should correctly identify that no path exists unless source equals destination.

The third edge case is large sparse graphs near the upper bound of n = 2 * 10^5. Recursive DFS would fail due to Python recursion limits, but BFS with a queue avoids stack overflow and handles the maximum input sizes efficiently. Our use of an adjacency list and visited array ensures performance scales linearly with the number of vertices and edges.