algoadvance

You are given an undirected graph represented by an integer n, indicating the number of nodes indexed from 0 to n-1, as well as a list edges where each edges[i] = [ui, vi] represents an undirected edge between node ui and node vi. You are also given two integers source and destination representing the start and end nodes, respectively.

Your task is to determine if there is a valid path from source to destination in the given graph. Return true if there is such a path, and false otherwise.

Clarifying Questions

  1. Are the edges bidirectional?
    • Yes, the problem specifies an “undirected” graph, meaning the edges are bidirectional.
  2. Can there be any cycles in the graph?
    • Yes, since it’s an undirected graph, there can be cycles.
  3. Is it guaranteed that source and destination are within the range [0, n-1]?
    • Yes, according to the problem statement.
  4. Can there be multiple edges between two nodes?
    • The problem does not specify, so we assume there can be multiple edges, though the typical assumption is no multiple edges unless explicitly stated.
  5. What is the expected size of the input?
    • Typically, n (number of nodes) can be up to 10^5 and the number of edges can be up to 2 * 10^5 based on standard constraints for similar problems.

Strategy

We can solve this problem using Depth-First Search (DFS) or Breadth-First Search (BFS) to explore the graph. Both methods are feasible:

  1. DFS Approach:
    • Use a stack and a boolean array to keep track of visited nodes.
    • Start from the source node and look for the destination node by iterating through the neighbors.
  2. BFS Approach:
    • Use a queue and a boolean array for visited nodes.
    • Explore level by level starting from the source node.

Both approaches guarantee that we will find a path from the source to the destination if one exists.

Time Complexity

Both DFS and BFS have a time complexity of O(n + e), where n is the number of nodes and e is the number of edges. This is because we visit each node and edge at most once.

Code

Let’s implement the BFS approach for finding whether a path exists in the graph:

def validPath(n, edges, source, destination):
    from collections import deque, defaultdict
    
    # Create an adjacency list
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    # Initialize a queue for BFS and a set to track visited nodes
    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

# Example Usage
n = 6
edges = [[0,1],[0,2],[3,5],[5,4],[4,3]]
source = 0
destination = 5

print(validPath(n, edges, source, destination))  # Output: False

This code uses a BFS approach to check if a path exists between the source and destination nodes. It uses an adjacency list to represent the graph and a queue to implement the BFS traversal. The complexity ensures that the solution will run efficiently even for the upper limits of typical graph problems on platforms like LeetCode.

Try our interview co-pilot at AlgoAdvance.com