We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find if Path Exists in Graph

Difficulty: Easy

Problem Description

Given a bi-directional graph with n vertices labeled from 0 to n - 1, and a list of edges representing connections between these vertices, determine if there is a valid path from a specified source vertex to a destination vertex.

Key Insights

  • The graph is bi-directional, meaning edges can be traversed in both directions.
  • Each vertex can be connected by at most one edge, and no vertex has an edge to itself.
  • The problem can be approached using graph traversal techniques like Depth-First Search (DFS) or Breadth-First Search (BFS).
  • The solution requires checking connectivity between two nodes in the graph.

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), for storing the graph as an adjacency list.

Solution

To determine if a path exists between the source and destination vertices, we can represent the graph using an adjacency list. From the source vertex, we perform a graph traversal (DFS or BFS) to explore all reachable vertices. If we reach the destination vertex during this traversal, it indicates that a path exists.

  1. Create an adjacency list to represent the graph.
  2. Use DFS or BFS to traverse from the source vertex.
  3. Keep track of visited vertices to avoid cycles.
  4. If the destination vertex is reached, return true; otherwise, return false.

Code Solutions

def validPath(n, edges, source, destination):
    from collections import defaultdict, deque
    
    # Step 1: Create an adjacency list
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    # Step 2: BFS to find path from source to destination
    queue = deque([source])
    visited = set([source])
    
    while queue:
        node = queue.popleft()
        if node == destination:
            return True
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return False
← Back to All Questions