Problem Description

You are given a bi-directional graph with n vertices labeled from 0 to n - 1. The graph is represented by a 2D array edges, where each edges[i] = [ui, vi] represents an undirected edge between vertices ui and vi.

The graph has the following properties:

• Each pair of vertices is connected by at most one edge (no multiple edges between the same pair)
• No vertex has an edge to itself (no self-loops)
• The edges are bi-directional, meaning you can travel from ui to vi and from vi to ui

Your task is to determine whether there exists a valid path from a given source vertex to a destination vertex. A valid path means you can travel from the source to the destination by following the edges in the graph.

The function should return true if such a path exists, and false otherwise.

Input:

• n: The number of vertices in the graph
• edges: A 2D array representing the edges in the graph
• source: The starting vertex
• destination: The target vertex

Output:

• true if there is a path from source to destination
• false if no such path exists

For example, if you have 3 vertices and edges [[0,1], [1,2]], there would be a path from vertex 0 to vertex 2 (going through vertex 1), but no direct path from vertex 0 to vertex 2 without going through vertex 1.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem explicitly states we have a graph with n vertices and edges connecting them. We need to find if a path exists between two vertices.

Is it a tree?

• No: The graph is not necessarily a tree. It could have cycles, disconnected components, or multiple paths between vertices. Trees have exactly n-1 edges for n vertices and no cycles, but this problem doesn't guarantee those properties.

Is the problem related to directed acyclic graphs?

• No: The graph is bi-directional (undirected), not a directed acyclic graph (DAG).

Is the problem related to shortest paths?

• No: We only need to determine if ANY valid path exists from source to destination, not the shortest one.

Does the problem involve connectivity?

• Yes: The core of the problem is determining if two vertices (source and destination) are connected by some path in the graph.

Disjoint Set Union

• While DSU could solve this connectivity problem, let's continue exploring other options based on the constraints.

Does the problem have small constraints?

• The constraints aren't explicitly mentioned as small, but for a connectivity problem, we can use DFS efficiently.

DFS/backtracking

• Yes: DFS is perfect for exploring paths in a graph to determine connectivity between two vertices.

Conclusion: The flowchart suggests using DFS (Depth-First Search) to explore the graph from the source vertex and determine if we can reach the destination vertex. This aligns perfectly with the solution approach, where we recursively explore neighbors until we either find the destination or exhaust all reachable vertices.

Intuition

When we need to check if two vertices are connected in a graph, we essentially need to explore all possible paths starting from the source vertex to see if we can reach the destination. This is a classic graph traversal problem.

Think of it like exploring a maze: you start at the entrance (source) and want to know if you can reach the exit (destination). The natural approach is to explore each path systematically - go as far as you can in one direction, and if you hit a dead end or a place you've already been, backtrack and try another path.

DFS is perfect for this because:

1. We only care about reachability, not the path itself - We just need a yes/no answer about whether a path exists
2. We can stop as soon as we find the destination - Unlike finding all paths or the shortest path, we can return immediately upon success
3. We need to avoid cycles - Since the graph might have cycles, we need to track visited vertices to avoid infinite loops

The key insight is that from any vertex, we recursively explore all its unvisited neighbors. If any neighbor leads to the destination (either directly or through further exploration), we've found a valid path. The recursion naturally handles the backtracking - when we can't proceed further from one neighbor, the recursive call returns and we try the next neighbor.

The solution builds an adjacency list from the edges to make neighbor lookup efficient (O(1) per vertex). Then, starting from the source, we mark vertices as visited and recursively explore. The base cases are:

• If we reach the destination, return true
• If we reach a visited vertex, return false (to avoid cycles)
• Otherwise, explore all neighbors and return true if any path succeeds

This approach guarantees we'll find a path if one exists, as DFS exhaustively explores all reachable vertices from the source.

Learn more about Depth-First Search, Breadth-First Search, Union Find and Graph patterns.

Solution Approach

The solution uses DFS to traverse the graph and determine if there's a path from source to destination. Let's walk through the implementation step by step:

1. Build the Adjacency List

First, we convert the edge list into an adjacency list representation for efficient neighbor lookup:

g = [[] for _ in range(n)]
for u, v in edges:
    g[u].append(v)
    g[v].append(u)

• We create a list g where g[i] contains all neighbors of vertex i
• Since the graph is bi-directional, we add both v to g[u] and u to g[v] for each edge

2. Initialize Visited Set

vis = set()

We use a set to track visited vertices, preventing cycles and redundant exploration.

3. Implement DFS Function

The recursive DFS function explores the graph:

def dfs(i: int) -> bool:
    if i == destination:
        return True
    if i in vis:
        return False
    vis.add(i)
    return any(dfs(j) for j in g[i])

The function works as follows:

• Base case 1: If current vertex i equals destination, we've found a path - return True
• Base case 2: If vertex i is already visited, return False to avoid cycles
• Recursive case: Mark vertex i as visited, then recursively explore all neighbors
  • The any() function returns True if at least one neighbor leads to the destination
  • This implements the backtracking naturally - if one path fails, we try the next neighbor

4. Start the Search

return dfs(source)

We initiate the DFS from the source vertex. The function will return True if any path to destination exists, False otherwise.

Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges. In the worst case, we visit every vertex and traverse every edge once.

Space Complexity: O(V) for the recursion stack and visited set in the worst case, plus O(E) for storing the adjacency list.

The elegance of this solution lies in its simplicity - the recursive DFS naturally handles path exploration and backtracking, while the visited set ensures we don't get stuck in cycles.

Example Walkthrough

Let's walk through a concrete example to understand how the DFS solution works.

Example Input:

• n = 6 (vertices labeled 0 to 5)
• edges = [[0,1], [0,2], [3,5], [5,4], [4,3]]
• source = 0
• destination = 5

Step 1: Build the Adjacency List

From the edges, we create:

g[0] = [1, 2]
g[1] = [0]
g[2] = [0]
g[3] = [5, 4]
g[4] = [5, 3]
g[5] = [3, 4]

This gives us two disconnected components:

• Component 1: vertices {0, 1, 2}
• Component 2: vertices {3, 4, 5}

Step 2: Initialize and Start DFS

• vis = {} (empty set initially)
• Call dfs(0) starting from source vertex 0

Step 3: DFS Execution

dfs(0):
  - Is 0 == 5? No
  - Is 0 in vis? No
  - Add 0 to vis: vis = {0}
  - Explore neighbors of 0: [1, 2]
  
    dfs(1):
      - Is 1 == 5? No
      - Is 1 in vis? No
      - Add 1 to vis: vis = {0, 1}
      - Explore neighbors of 1: [0]
      
        dfs(0):
          - Is 0 == 5? No
          - Is 0 in vis? Yes → return False
    
      - No unvisited neighbors lead to destination
      - return False
  
    dfs(2):
      - Is 2 == 5? No
      - Is 2 in vis? No
      - Add 2 to vis: vis = {0, 1, 2}
      - Explore neighbors of 2: [0]
      
        dfs(0):
          - Is 0 == 5? No
          - Is 0 in vis? Yes → return False
    
      - No unvisited neighbors lead to destination
      - return False

  - Neither neighbor (1 or 2) leads to destination
  - any([False, False]) = False
  - return False

Result: The function returns False because vertices 0 and 5 are in different connected components with no path between them.

Alternative Example with Path:

If we had source = 3 and destination = 4 instead:

dfs(3):
  - Is 3 == 4? No
  - Is 3 in vis? No
  - Add 3 to vis: vis = {3}
  - Explore neighbors of 3: [5, 4]
  
    dfs(5):
      - Is 5 == 4? No
      - Is 5 in vis? No
      - Add 5 to vis: vis = {3, 5}
      - Continue exploring...
  
    dfs(4):
      - Is 4 == 4? Yes → return True!

  - any([..., True]) = True
  - return True

The function would return True because vertex 4 is a direct neighbor of vertex 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m)

The algorithm uses depth-first search (DFS) to find a path from source to destination. Breaking down the time complexity:

• Building the adjacency list: We iterate through all m edges once, and for each edge, we perform two constant-time append operations. This takes O(m) time.
• DFS traversal: In the worst case, we visit each of the n nodes at most once (thanks to the visited set check). For each visited node, we explore all its adjacent edges. Since each edge connects two nodes, the total number of adjacencies across all nodes is 2m. Therefore, the DFS takes O(n + m) time.
• Overall: O(m) + O(n + m) = O(n + m)

Space Complexity: O(n + m)

The space usage consists of:

• Adjacency list g: Contains n empty lists initially, and stores a total of 2m edge references (each edge (u, v) is stored twice: once in g[u] and once in g[v]). This requires O(n + m) space.
• Visited set vis: Can contain at most n nodes, requiring O(n) space.
• Recursion call stack: In the worst case (e.g., a linear chain of nodes), the DFS recursion depth can be O(n).
• Overall: O(n + m) + O(n) + O(n) = O(n + m)

Where n is the number of nodes and m is the number of edges in the graph.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Disconnected Components

A common mistake is assuming the graph is connected. If source and destination are in different connected components, no path exists between them. While the DFS solution handles this correctly by returning False when all reachable nodes are explored, developers might incorrectly assume they need special handling for disconnected graphs.

Example scenario:

n = 6
edges = [[0,1], [0,2], [3,4], [4,5]]  # Two disconnected components
source = 0
destination = 5
# Returns False correctly, but some might think additional logic is needed

2. Stack Overflow in Deep Recursion

For graphs with very long paths or large numbers of vertices, the recursive DFS can cause stack overflow. Python has a default recursion limit (usually 1000), which can be exceeded in certain graph structures.

Solution: Use iterative DFS with an explicit stack:

def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
    # Build adjacency list
    adjacency_list = [[] for _ in range(n)]
    for u, v in edges:
        adjacency_list[u].append(v)
        adjacency_list[v].append(u)
  
    # Iterative DFS using stack
    stack = [source]
    visited = set()
  
    while stack:
        current = stack.pop()
      
        if current == destination:
            return True
          
        if current in visited:
            continue
          
        visited.add(current)
      
        for neighbor in adjacency_list[current]:
            if neighbor not in visited:
                stack.append(neighbor)
  
    return False

3. Edge Case: source == destination

When the source and destination are the same vertex, the path trivially exists. The current solution handles this correctly (returns True immediately), but some implementations might overlook this edge case or add unnecessary complexity.

Quick optimization:

# Add this check before starting DFS
if source == destination:
    return True

4. Not Using Early Termination in any()

The current solution correctly uses any() with a generator expression, which provides early termination. However, a common mistake is to use a list comprehension instead:

Wrong approach:

# This evaluates ALL neighbors even if first one finds the path
return any([dfs(neighbor) for neighbor in adjacency_list[current_node]])

Correct approach (as in the solution):

# Generator expression - stops as soon as True is found
return any(dfs(neighbor) for neighbor in adjacency_list[current_node])

5. Memory Issues with Large Sparse Graphs

For very large values of n with few edges (sparse graphs), creating an adjacency list with n empty lists can be memory-inefficient.

Alternative using dictionary:

from collections import defaultdict

adjacency_list = defaultdict(list)
for u, v in edges:
    adjacency_list[u].append(v)
    adjacency_list[v].append(u)

This only creates entries for vertices that actually have edges, saving memory in sparse graphs.