LeetCode Solutions Blog

Find if Path Exists in Graph

Number: 2121

Difficulty: Easy

Paid? No

Problem Description

Given an undirected graph with n vertices labeled from 0 to n - 1 and an edge list representing bi-directional connections, determine if there exists a valid path from the source vertex to the destination vertex.

Key Insights

The graph is undirected, meaning each edge can be traversed in both directions.
Graph traversal algorithms such as DFS or BFS can be used to explore connectivity.
Alternative approach using Union Find (Disjoint Set Union) is also effective for connectivity problems.
Building an efficient adjacency list is key for handling large graphs.

Space and Time Complexity

Time Complexity: O(n + E), where n is the number of vertices and E is the number of edges.
Space Complexity: O(n + E), due to the storage of the adjacency list and auxiliary data structures (stack/queue, visited set).

Solution

We first construct an adjacency list from the provided list of edges. Then, we use a DFS (or alternatively, BFS) to traverse the graph starting from the source vertex. During the traversal, we mark each vertex as visited to avoid cycles. If we reach the destination, we return true; if the traversal completes without finding the destination, we return false.

Code Solutions

# Python code for finding if a path exists in an undirected graph
def validPath(n, edges, source, destination):
    # Build the adjacency list for the graph
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    # Helper function using DFS to explore the graph
    def dfs(current, destination, visited):
        # Check if the current vertex is the destination
        if current == destination:
            return True
        # Mark the current vertex as visited
        visited.add(current)
        # Visit all neighbors
        for neighbor in graph[current]:
            if neighbor not in visited:
                if dfs(neighbor, destination, visited):
                    return True
        return False

    # Use DFS starting from the source vertex and an empty set for visited nodes
    return dfs(source, destination, set())

# Example usage:
n = 3
edges = [[0, 1], [1, 2], [2, 0]]
source = 0
destination = 2
print(validPath(n, edges, source, destination))  # Expected output: True