Hello, reader 👋🏽 ! Welcome to day 79 of the series on Problem Solving. Through this series, I aim to pick up at least one question every day and share my approach to solving it.
Today, I will be picking up LeetCode's daily challenge problem: 1971. Find if Path Exists in Graph.
🤔 Problem Statement
There is a bi-directional graph with
nvertices, where each vertex is labelled from0ton - 1(inclusive).The edges in the graph are represented as a 2D integer array
edges, where eachedges[i] = [ui, vi]denotes a bi-directional edge between the vertexuiand vertexvi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.Given
edgesand the integersn,source, anddestination, returntrueif there is a valid path from the source todestination, orfalseotherwise.E.g.:
n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2 => true n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5 => false
I will be sharing three different approaches to solving this problem:
Depth First Search (DFS)
Breadth First Search (BFS)
Union find
💬 Thought Process - DFS
This problem can be solved by generating an adjacency list which would contain the list of neighbours for every node
i.To build the adjacency list, we will have to first declare a list of lists with n slots. Each index
iin the list would represent the node and its value would be a list containing all the neighbours ofi.Once we have the adjacency list, the next step is to iterate through the graph starting from the
sourcenode.From the
source, we will traverse to all the neighbours ofsource, then the neighbours of neighbours ofsourceand so on.- Meaning that we would go depth-wise from the source node until all nodes have been visited.
The traversal will be similar to the classic DFS traversal with only one change. At every traversal, we will check if the current node is the
destinationnode.If yes, then we will return true and stop iterating
If not, we keep traversing to all the neighbours and will stop any time the traversal of any neighbour returns true.
👩🏽💻 Solution - DFS
- Below is the code for the approach for solving this problem using a DFS traversal.
class Solution {
private List<List<Integer>> adj;
private Set<Integer> visited;
public boolean validPath(int n, int[][] edges,
int source, int destination)
{
adj = new ArrayList();
for(int i = 0; i<n; i++) {
adj.add(new ArrayList());
}
generateAdjList(edges);
visited = new HashSet();
return dfs(source, destination);
}
private void generateAdjList(int[][] edges) {
for(int[] edge: edges) {
int u = edge[0];
int v = edge[1];
adj.get(u).add(v);
adj.get(v).add(u);
}
}
private boolean dfs(int source, int destination) {
visited.add(source);
if(source == destination) return true;
for(int node: adj.get(source)) {
if(!visited.contains(node)) {
if(dfs(node, destination)) return true;
}
}
return false;
}
}
Time Complexity: O(v + e)
- e = number of edges
- v = number of vertices
Space Complexity: O(v + e)
- e = number of edges
- v = number of vertices
💬 Thought Process - BFS
The other way to solve this problem is using the breadth-first search traversal.
We would again have to build an adjacency list representing the list of neighbours for every node.
Once we have the adjacency list, the next step is to iterate through the graph starting from the
sourcenode using a queue.We will add the
sourceto the queue and then traverse the graph by traversing the immediate neighbours first and then the neighbours of all the previous nodes.The traversal will be similar to the classic BFS traversal with only one change. At every traversal, we will check if the current node is the
destinationnode.If yes, then we will return true and stop iterating
If not, we continue traversing to all the neighbours
👩🏽💻 Solution - BFS
- Below is the code for the approach for solving this problem using a BFS traversal.
class Solution {
private List<List<Integer>> adj;
private Set<Integer> visited;
public boolean validPath(int n, int[][] edges,
int source, int destination) {
adj = new ArrayList();
for(int i = 0; i<n; i++) {
adj.add(new ArrayList());
}
generateAdjList(edges);
visited = new HashSet();
return bfs(source, destination);
}
private void generateAdjList(int[][] edges) {
for(int[] edge: edges) {
int u = edge[0];
int v = edge[1];
adj.get(u).add(v);
adj.get(v).add(u);
}
}
private boolean bfs(int source, int destination) {
Queue<Integer> nodes = new LinkedList();
nodes.add(source);
visited.add(source);
while(!nodes.isEmpty()) {
int currNode = nodes.poll();
if(currNode == destination) {
return true;
}
for(int nextNode: adj.get(currNode)) {
if(!visited.contains(nextNode)) {
visited.add(nextNode);
nodes.add(nextNode);
}
}
}
return false;
}
}
Time Complexity: O(v + e)
- e = number of edges
- v = number of vertices
Space Complexity: O(v + e)
- e = number of edges
- v = number of vertices
💬 Thought Process - Union Find
A better and optimised solution is to use the union find/ disjoint set data structure.
If you are unaware of disjoint sets, one of the finest explanations is available on Leetcode in the explore section: Disjoint Set Explore
We will use path compression and union by rank to optimize the time complexity and find if the
sourceanddestinationnodes are connected.Using the
UnionFindclass, we will make use of three methods:union(int x, int y)=> connects x and y using rankfind(int x)=> find if x and y are connected using path compressionareConnected(int x, int y)=> check if x and y are connected
Basically, we would have a parent and rank array of size
n, and traverse every edge to connect them using theunion()method.Then finally to check if the
sourceanddestinationare connected, we will call theareConnected()method whose return value would indicate if the two nodes are connected or not.Since at every
find()call, there will be path compression, i.e. the root of the component would be the parent for every nodeuin the component, we can easily figure out ifxandyare connected based on theparent[x]andparent[y].
👩🏽💻 Solution - BFS
- Below is the code for the approach for solving this problem using a BFS traversal.
class UnionFind {
int n;
int[] rank, parent;
UnionFind(int n) {
this.n = n;
rank = new int[n];
parent = new int[n];
for(int i = 0; i<n; i++) {
rank[i] = 0;
parent[i] = i;
}
}
private int find(int x) {
// Path compression
if(parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
public void union(int x, int y) {
int parX = find(x);
int parY = find(y);
// union by rank
if(parX != parY) {
if(rank[parX] > rank[parY]) {
parent[parY] = parX;
}
else if(rank[parY] > rank[parX]) {
parent[parX] = parY;
}
else {
parent[parY] = parX;
rank[parX] += 1;
}
}
}
public boolean isConnected(int x, int y) {
return find(x) == find(y);
}
}
class Solution {
public boolean validPath(int n, int[][] edges,
int source, int destination)
{
UnionFind uf = new UnionFind(n);
for(int[] edge: edges) {
uf.union(edge[0], edge[1]);
}
return uf.isConnected(source, destination);
}
}
Time Complexity: O(e * (v * alpha))
- e = number of edges
- v = number of vertices
- alpha = inverse of Ackermann function
Space Complexity: O(v)
- v = number of vertices
NOTE: If you did not understand the union-find approach, I highly recommend the explore section of Leetcode. The explanation is top-notch!
- You can find the link to the GitHub repo for this question here: 1971. Find if Path Exists in Graph.
Conclusion
That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!
Thank you for reading!