Find if Path Exists in Graph

The task is to determine if there is a valid path from a given source vertex to a destination vertex in a graph. The vertices are labeled from 0 to n-1. The edges are given in a 2D integer array where each sub-array represents a bidirectional edge between two vertices.

You can approach this problem using a technique called Depth-First Search (DFS). This technique is used to traverse or search through a graph in a depthward motion and uses a stack data structure to remember to get the next vertex to start a search when a dead-end occurs in any iteration.

Here is a step by step approach to solve this problem:

  1. Create an adjacency list to represent the graph. An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph.

  2. Use Depth-First Search (DFS) to find a path from the source to the destination. Starting from the source, recursively visit each node that is adjacent to the current node and not already visited.

  3. If you reach the destination node during the DFS traversal, that means there is a path from source to destination. So, return True.

  4. If the DFS ends without visiting the destination, that means no valid path exists, and you can return False.

Here is the Python implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

from collections import defaultdict
class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        stack = [source]
        visited = set()
        while stack:
            node = stack.pop()
            visited.add(node)
            if node == destination:
                return True
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

        return False

This algorithm works within the given constraints. The time complexity is O(n + e) where n is the number of vertices and e is the number of edges in the graph. The space complexity is O(n + e) to store the adjacency list and the visited set.