Find if Path Exists in Graph Interview Question for Google

You are given a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex source to vertex destination.

Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.

Here are a couple of examples:

Example 1: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2 Output: true Explanation: There are two paths from vertex 0 to vertex 2:

0 → 1 → 2
0 → 2

Example 2: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5 Output: false Explanation: There is no path from vertex 0 to vertex 5.

Could you implement a function to solve this problem efficiently? What is the time and space complexity of your solution? Also, consider edge cases where the source and destination are the same, or when the graph is disconnected.

Valid Path in a Graph

Problem Description

Given a bidirectional graph represented by a list of edges, determine if there is a valid path from a source vertex to a destination vertex.

Naive Approach: Breadth-First Search (BFS) or Depth-First Search (DFS)

The most straightforward approach is to use either Breadth-First Search (BFS) or Depth-First Search (DFS) to traverse the graph starting from the source vertex. We mark visited nodes to avoid cycles. If we reach the destination vertex during the traversal, we return true; otherwise, if we exhaust all reachable nodes without finding the destination, we return false.

Algorithm

Create an adjacency list representation of the graph from the given edges.
Initialize a visited set to keep track of visited nodes.
Start a BFS or DFS traversal from the source node.
During the traversal, if we encounter the destination node, return true.
If the traversal finishes without finding the destination, return false.

Code (Python - BFS)

from collections import deque

def has_path(n, edges, source, destination):
    adj_list = [[] for _ in range(n)]
    for u, v in edges:
        adj_list[u].append(v)
        adj_list[v].append(u)

    visited = set()
    queue = deque([source])
    visited.add(source)

    while queue:
        node = queue.popleft()
        if node == destination:
            return True

        for neighbor in adj_list[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return False

Time Complexity

O(V + E), where V is the number of vertices and E is the number of edges.

Space Complexity

O(V + E) in the worst case. O(V) for visited set, and O(E) since we are storing the adjancency list.

Optimal Solution: Same as Naive Approach

For this problem, BFS and DFS are already quite efficient and optimal for determining path existence in a graph. There is not a fundamentally different approach that provides a significant improvement in time complexity. The key is using a visited set to avoid redundant work from infinite loops.

Edge Cases

Source equals Destination: If the source and destination are the same, return true immediately.
Empty graph (no edges): If there are no edges, return true only if the source and destination are the same.
Disconnected graph: The algorithm handles disconnected graphs correctly because it explores only the connected component containing the source.

Summary

BFS or DFS provides an efficient solution with a time complexity of O(V + E). The space complexity is O(V + E) mainly due to the storage of the graph's adjacency list and the visited set. The algorithm correctly handles various edge cases, including when source and destination are the same, when there are no edges, and for disconnected graphs.