Find if there is a path between two vertices in a directed graph

Problem

Given a directed graph with n vertices and two vertices source and destination, check whether there is a path from the source vertex to the destination vertex.

The graph is represented as an adjacency list where graph[i] contains all vertices that vertex i has directed edges to.

Return true if there is a valid directed path from source to destination, false otherwise.

Examples

Example 1

Input: n = 4, edges = [[0,1],[1,2],[2,3]], source = 0, destination = 3
Output: true
Explanation: There is a path from vertex 0 to vertex 3: 0 → 1 → 2 → 3

Example 2

Input: n = 4, edges = [[0,1],[2,3]], source = 0, destination = 3
Output: false
Explanation: There is no path from vertex 0 to vertex 3. They are in different components.

Example 3

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 1, destination = 0
Output: true
Explanation: There is a cycle, and vertex 0 is reachable from vertex 1: 1 → 2 → 0

Similar Problem

This problem is similar to [Find if Path Exists in Graph](find-if-path-exists-in-graph), but here the graph is directed (uni-directional) whereas there it is undirected (bi-directional).

Solutions

Method 1 - Depth-First Search (DFS)

Intuition

Use DFS to traverse the directed graph starting from the source vertex. If we can reach the destination vertex during traversal, return true. Use a visited set to avoid cycles.

Approach

1. Build adjacency list: Create a directed graph representation
2. DFS traversal: Start from source and explore all reachable vertices
3. Cycle detection: Use visited set to avoid infinite loops
4. Early termination: Return true immediately when destination is found

Code

C++

#include <vector>
#include <unordered_set>
#include <unordered_map>

class Solution {
public:
    bool validPath(int n, std::vector<std::vector<int>>& edges, int source, int destination) {
        if (source == destination) return true;
        
        // Build directed adjacency list
        std::unordered_map<int, std::vector<int>> graph;
        for (const auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
        }
        
        std::unordered_set<int> visited;
        return dfs(graph, source, destination, visited);
    }
    
private:
    bool dfs(std::unordered_map<int, std::vector<int>>& graph, 
             int current, int destination, std::unordered_set<int>& visited) {
        if (current == destination) return true;
        if (visited.count(current)) return false;
        
        visited.insert(current);
        
        for (int neighbor : graph[current]) {
            if (dfs(graph, neighbor, destination, visited)) {
                return true;
            }
        }
        
        return false;
    }
};

Go

func validPath(n int, edges [][]int, source int, destination int) bool {
    if source == destination {
        return true
    }
    
    // Build directed adjacency list
    graph := make(map[int][]int)
    for _, edge := range edges {
        graph[edge[0]] = append(graph[edge[0]], edge[1])
    }
    
    visited := make(map[int]bool)
    return dfs(graph, source, destination, visited)
}

func dfs(graph map[int][]int, current, destination int, visited map[int]bool) bool {
    if current == destination {
        return true
    }
    
    if visited[current] {
        return false
    }
    
    visited[current] = true
    
    for _, neighbor := range graph[current] {
        if dfs(graph, neighbor, destination, visited) {
            return true
        }
    }
    
    return false
}

Java

import java.util.*;

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        if (source == destination) return true;
        
        // Build directed adjacency list
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
        }
        
        Set<Integer> visited = new HashSet<>();
        return dfs(graph, source, destination, visited);
    }
    
    private boolean dfs(Map<Integer, List<Integer>> graph, int current, 
                       int destination, Set<Integer> visited) {
        if (current == destination) return true;
        if (visited.contains(current)) return false;
        
        visited.add(current);
        
        for (int neighbor : graph.get(current)) {
            if (dfs(graph, neighbor, destination, visited)) {
                return true;
            }
        }
        
        return false;
    }
}

Kotlin

class Solution {
    fun validPath(n: Int, edges: Array<IntArray>, source: Int, destination: Int): Boolean {
        if (source == destination) return true
        
        // Build directed adjacency list
        val graph = mutableMapOf<Int, MutableList<Int>>()
        repeat(n) { graph[it] = mutableListOf() }
        
        for (edge in edges) {
            graph[edge[0]]!!.add(edge[1])
        }
        
        val visited = mutableSetOf<Int>()
        return dfs(graph, source, destination, visited)
    }
    
    private fun dfs(graph: Map<Int, List<Int>>, current: Int, 
                   destination: Int, visited: MutableSet<Int>): Boolean {
        if (current == destination) return true
        if (current in visited) return false
        
        visited.add(current)
        
        for (neighbor in graph[current] ?: emptyList()) {
            if (dfs(graph, neighbor, destination, visited)) {
                return true
            }
        }
        
        return false
    }
}

Python

from collections import defaultdict
from typing import List, Set, Dict

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        if source == destination:
            return True
        
        # Build directed adjacency list
        graph: Dict[int, List[int]] = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
        
        visited: Set[int] = set()
        return self.dfs(graph, source, destination, visited)
    
    def dfs(self, graph: Dict[int, List[int]], current: int, 
            destination: int, visited: Set[int]) -> bool:
        if current == destination:
            return True
        
        if current in visited:
            return False
        
        visited.add(current)
        
        for neighbor in graph[current]:
            if self.dfs(graph, neighbor, destination, visited):
                return True
        
        return False

# Alternative iterative DFS implementation
class SolutionIterative:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        if source == destination:
            return True
        
        # Build directed adjacency list
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
        
        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 graph[current]:
                if neighbor not in visited:
                    stack.append(neighbor)
        
        return False

Rust

use std::collections::{HashMap, HashSet};

impl Solution {
    pub fn valid_path(n: i32, edges: Vec<Vec<i32>>, source: i32, destination: i32) -> bool {
        if source == destination {
            return true;
        }
        
        // Build directed adjacency list
        let mut graph: HashMap<i32, Vec<i32>> = HashMap::new();
        for i in 0..n {
            graph.insert(i, Vec::new());
        }
        
        for edge in &edges {
            if let Some(neighbors) = graph.get_mut(&edge[0]) {
                neighbors.push(edge[1]);
            }
        }
        
        let mut visited = HashSet::new();
        Self::dfs(&graph, source, destination, &mut visited)
    }
    
    fn dfs(graph: &HashMap<i32, Vec<i32>>, current: i32, destination: i32, visited: &mut HashSet<i32>) -> bool {
        if current == destination {
            return true;
        }
        
        if visited.contains(&current) {
            return false;
        }
        
        visited.insert(current);
        
        if let Some(neighbors) = graph.get(&current) {
            for &neighbor in neighbors {
                if Self::dfs(graph, neighbor, destination, visited) {
                    return true;
                }
            }
        }
        
        false
    }
}

TypeScript

function validPath(n: number, edges: number[][], source: number, destination: number): boolean {
    if (source === destination) return true;
    
    // Build directed adjacency list
    const graph: Map<number, number[]> = new Map();
    for (let i = 0; i < n; i++) {
        graph.set(i, []);
    }
    
    for (const [u, v] of edges) {
        graph.get(u)!.push(v);
    }
    
    const visited: Set<number> = new Set();
    return dfs(graph, source, destination, visited);
}

function dfs(graph: Map<number, number[]>, current: number, 
            destination: number, visited: Set<number>): boolean {
    if (current === destination) return true;
    if (visited.has(current)) return false;
    
    visited.add(current);
    
    for (const neighbor of graph.get(current) || []) {
        if (dfs(graph, neighbor, destination, visited)) {
            return true;
        }
    }
    
    return false;
}

Complexity

• ⏰ Time complexity: O(V + E) where V is the number of vertices and E is the number of edges
• 🧺 Space complexity: O(V) for the visited set and recursion stack

Method 2 - Breadth-First Search (BFS)

Intuition

Use BFS to explore the directed graph level by level starting from the source vertex. BFS guarantees finding the shortest path if one exists.

Approach

1. Build adjacency list: Create directed graph representation
2. Level-order traversal: Use queue to explore vertices level by level
3. Visited tracking: Mark vertices to avoid revisiting
4. Early termination: Return true when destination is found

Code

Java

import java.util.*;

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        if (source == destination) return true;
        
        // Build directed adjacency list
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
        }
        
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        
        queue.offer(source);
        visited.add(source);
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            
            for (int neighbor : graph.get(current)) {
                if (neighbor == destination) return true;
                
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        
        return false;
    }
}

Python

from collections import deque, defaultdict
from typing import List

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        if source == destination:
            return True
        
        # Build directed adjacency list
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
        
        queue = deque([source])
        visited = {source}
        
        while queue:
            current = queue.popleft()
            
            for neighbor in graph[current]:
                if neighbor == destination:
                    return True
                
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        return False

Complexity

• ⏰ Time complexity: O(V + E) where V is the number of vertices and E is the number of edges
• 🧺 Space complexity: O(V) for the queue and visited set

Analysis

Key differences from undirected graph path finding:

• Direction matters: Only traverse edges in their specified direction
• Asymmetric reachability: A→B doesn't guarantee B→A
• Cycle handling: Directed cycles don't affect the algorithm complexity

When to use each approach:

• Use DFS when you want to explore deeply and memory is a concern
• Use BFS when you want to find the shortest path or explore systematically

Both approaches have the same time and space complexity for this problem, so the choice often comes down to personal preference or specific requirements.