Find if Path Exists in Directed Graph

Problem

There is 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_._

Examples

Example 1:

graph LR;
	0 --> 1 --> 2 --> 0

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

Example 2:

graph LR;
	2 <-- 0 --> 1
	3 --> 5 --> 4 --> 3

Input: 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.

Similar Problem

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

Solutions

Method 1 - BFS

BFS can be used to check if one node is reachable from other :

Add V1 to a queue of nodes to be visited
While there are nodes in the queue:
    If the node is V2, return true
    Mark the node as visited
    For every node at the end of an outgoing edge which is not yet visited:
        Add this node to the queue
    End for
End while
Return false

Code

Java

public boolean validPath(int n, int[][] edges, int source, int destination) {
	if (source == destination) {
		return true;
	}
	Map<Integer, List<Integer>> g = new HashMap<>();
	for (int i = 0; i < n; i++) {
		g.put(i, new LinkedList<>());
	}
	for (int[] edge: edges) {
		int src = edge[0];
		int dest = edge[1];
		// uni-directioanl, so just 1 edge
		g.get(src).add(dest);
	}
	Queue<Integer> queue = new LinkedList();
	queue.add(source);
	Set<Integer> visited = new HashSet<>();
	while(!queue.isEmpty()) {
		int curr = queue.poll();
		visited.add(curr);
		for(int nei: g.get(curr)) {
			if (nei == destination) {
				return true;
			}
			if (visited.contains(nei)) {
				continue;
			}
			queue.add(nei);
		}
	}
	return false;
}

Method 2 - DFS

Code

Java

public boolean validPath(int n, int[][] edges, int source, int destination) {
	if (source == destination) {
		return true;
	}
	Map<Integer, List<Integer>> g = new HashMap<>();
	for (int i = 0; i < n; i++) {
		g.put(i, new LinkedList<>());
	}
	for (int[] edge: edges) {
		int src = edge[0];
		int dest = edge[1];
		// uni-directioanl, so just 1 edge
		g.get(src).add(dest);
	}
	Stack<Integer> stk = new Stack<>();
	stk.add(source);
	Set<Integer> visited = new HashSet<>();
	while(!stk.isEmpty()) {
		int curr = stk.pop();
		visited.add(curr);
		for(int nei: g.get(curr)) {
			if (nei == destination) {
				return true;
			}
			if (visited.contains(nei)) {
				continue;
			}
			stk.add(nei);
		}
	}
	return false;
}

Method 3 - Union Find OR Disjoint Set

Code

Java

class DisjointSetUnion{
    private int[] parent;
    private int[] rank;
    private int N;
    
    public DisjointSetUnion(int n){
        this.N = n;
        this.parent = new int[this.N];
        this.rank = new int[this.N];
        for(int i = 0; i < this.N; i++){
            this.parent[i] = i;
            this.rank[i] = 1;
        }
    }
    
    public boolean areConnected(int u, int v){
        return find(u) == find(v);
    }
    
    public void union(int u, int v){
        if(u != v){
            int a = find(u);
            int b = find(v);
            if(a != b){
                if(rank[a] > rank[b]){
                    parent[b] = a;
                    rank[a] += rank[b];
                }else{
                    parent[a] = b;
                    rank[b] += rank[a];
                }
            }
        }
    }
    
    private int find(int u){
        int x = u;
        while(x != this.parent[x]){
            x = this.parent[x];
        }
        
        this.parent[u] = x;
        return x;
    }
}

class Solution {
    public boolean validPath(int n, int[][] edges, int start, int end) {
        DisjointSetUnion set = new DisjointSetUnion(n);
        for(int[] edge : edges){
            set.union(edge[0], edge[1]);
        }
        
        return set.areConnected(start, end);
    }
}

Complexity

• Time complexity = O(E log V)