Problem of The Day: Find if Path Exists in Graph

Problem Statement

Intuition

I’m thinking about using a breadth-first search (BFS) algorithm to explore the graph starting from the source node. BFS allows us to systematically explore nodes level by level, which can help in finding a valid path from the source to the destination.

Approach

I’ll start by creating an adjacency list representation of the graph using a dictionary. Then, I’ll use a queue to perform BFS. At each step, I’ll dequeue a node, check if it’s the destination node, and if not, enqueue its unvisited neighbors. I’ll repeat this process until either the destination node is found or the queue becomes empty.

Complexity

• Time complexity: O(V + E) where V is the number of vertices and E is the number of edges

• Space complexity: O(V)

Code

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        graph = {i: [] for i in range(n)}
        for src, des in edges:
            graph[src].append(des)
            graph[des].append(src)
        queue = deque([source])
        visited = set()
        visited.add(source)
        while queue:
            node = queue.popleft()
            if node == destination:
                return True
            visited.add(node)
            for nei in graph[node]:
                if nei not in visited:
                    queue.append(nei)
                    visited.add(nei)

        return False