Given an undirected graph with N vertices and E edges and two vertices (U, V) from the graph, the task is to detect if a path exists between these two vertices. Print “Yes” if a path exists and “No” otherwise.
Examples:
U = 1, V = 2
Output: No
Explanation:
There is no edge between the two points and hence its not possible to reach 2 from 1.Input:
U = 1, V = 3
Output: Yes
Explanation: Vertex 3 from vertex 1 via vertices 2 or 4.
Naive Approach:
The idea is to use Floyd Warshall Algorithm. To solve the problem, we need to try out all intermediate vertices ranging [1, N] and check:
- If there is a direct edge already which exists between the two nodes.
- Or we have a path from node i to intermediate node k and from node k to node j.
Below is the implementation of the above approach:
C++
// C++ program to check if there is exist a path between// two vertices of an undirected graph.#include<bits/stdc++.h>using namespace std;vector<vector<int>> adj;// function to initialise // the adjacency matrixvoid init(int n){ for(int i=1;i<=n;i++) adj[i][i]=1;}// Function to add edge between nodesvoid addEdge(int a,int b){ adj[a][b]=1; adj[b][a]=1;}// Function to compute the pathvoid computePaths(int n){ // Use Floyd Warshall algorithm // to detect if a path exists for(int k = 1; k <= n; k++) { // Try every vertex as an // intermediate vertex // to check if a path exists for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) adj[i][j] = adj[i][j] | (adj[i][k] && adj[k][j]); }}// Function to check if nodes are reachablebool isReachable(int s, int d){ if (adj[s][d] == 1) return true; else return false;}// Driver Codeint main(){ int n = 4; adj = vector<vector<int>>(n+1,vector<int>(n+1,0)); init(n); addEdge(1,2); addEdge(2,3); addEdge(1,4); computePaths(n); int u = 4, v = 3; if(isReachable(u,v)) cout << "Yes\n"; else cout << "No\n"; return 0;} |
Java
// Java program to detect if a path// exists between any two vertices// for the given undirected graphimport java.util.Arrays;public class GFG{// Class representing a undirected// graph using matrix representationstatic class Graph{ int V; int[][] g; public Graph(int V) { this.V = V; // Rows may not be contiguous g = new int[V + 1][V + 1]; for(int i = 0; i < V + 1; i++) { // Initialize all entries // as false to indicate // that there are // no edges initially Arrays.fill(g[i], 0); } // Initializing node to itself // as it is always reachable for(int i = 1; i <= V; i++) g[i][i] = 1; } // Function to add edge between nodes void addEdge(int v, int w) { g[v][w] = 1; g[w][v] = 1; } // Function to check if nodes are reachable boolean isReachable(int s, int d) { if (g[s][d] == 1) return true; else return false; } // Function to compute the path void computePaths() { // Use Floyd Warshall algorithm // to detect if a path exists for(int k = 1; k <= V; k++) { // Try every vertex as an // intermediate vertex // to check if a path exists for(int i = 1; i <= V; i++) { for(int j = 1; j <= V; j++) g[i][j] = g[i][j] | ((g[i][k] != 0 && g[k][j] != 0) ? 1 : 0); } } }};// Driver codepublic static void main(String[] args) { Graph _g = new Graph(4); _g.addEdge(1, 2); _g.addEdge(2, 3); _g.addEdge(1, 4); _g.computePaths(); int u = 4, v = 3; if (_g.isReachable(u, v)) System.out.println("Yes"); else System.out.println("No");}}// This code is contributed by sanjeev2552 |
Python3
# Python3 program to detect if a path # exists between any two vertices # for the given undirected graph # Class representing a undirected # graph using matrix # representation class Graph: def __init__(self, V): self.V = V # Initialize all entries # as false to indicate # that there are # no edges initially self.g = [[0 for j in range(self.V + 1)] for i in range(self.V + 1)] # Initializing node to itself # as it is always reachable for i in range(self.V + 1): self.g[i][i] = 1 # Function to add edge between nodes def addEdge(self, v, w): self.g[v][w] = 1 self.g[w][v] = 1 # Function to compute the path def computePaths(self): # Use Floyd Warshall algorithm # to detect if a path exists for k in range(1, self.V + 1): # Try every vertex as an # intermediate vertex # to check if a path exists for i in range(1, self.V + 1): for j in range(1, self.V + 1): self.g[i][j] = (self.g[i][j] | (self.g[i][k] and self.g[k][j])) # Function to check if nodes # are reachable def isReachable(self, s, d): if (self.g[s][d] == 1): return True else: return False # Driver code if __name__=='__main__': _g = Graph(4) _g.addEdge(1, 2) _g.addEdge(2, 3) _g.addEdge(1, 4) _g.computePaths() u = 4 v = 3 if (_g.isReachable(u, v)): print('Yes') else: print('No') # This code is contributed by rutvik_56 |
C#
// C# program to detect if a path// exists between any two vertices// for the given undirected graphusing System;public class GFG { // Class representing a undirected // graph using matrix representation public class Graph { public int V; public int[, ] g; public Graph(int V) { this.V = V; // Rows may not be contiguous g = new int[V + 1, V + 1]; for (int i = 0; i < V + 1; i++) { // Initialize all entries // as false to indicate // that there are // no edges initially for (int j = 0; j < V + 1; j++) g[i, j] = 0; } // Initializing node to itself // as it is always reachable for (int i = 1; i <= V; i++) g[i, i] = 1; } // Function to add edge between nodes public void addEdge(int v, int w) { g[v, w] = 1; g[w, v] = 1; } // Function to check if nodes are reachable public bool isReachable(int s, int d) { if (g[s, d] == 1) return true; else return false; } // Function to compute the path public void computePaths() { // Use Floyd Warshall algorithm // to detect if a path exists for (int k = 1; k <= V; k++) { // Try every vertex as an // intermediate vertex // to check if a path exists for (int i = 1; i <= V; i++) { for (int j = 1; j <= V; j++) g[i, j] = g[i, j] | ((g[i, k] != 0 && g[k, j] != 0) ? 1 : 0); } } } }; // Driver code public static void Main(String[] args) { Graph _g = new Graph(4); _g.addEdge(1, 2); _g.addEdge(2, 3); _g.addEdge(1, 4); _g.computePaths(); int u = 4, v = 3; if (_g.isReachable(u, v)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code is contributed by umadevi9616 |
Javascript
<script>// Javascript program to detect if a path// exists between any two vertices// for the given undirected graph// Class representing a undirected// graph using matrix representationclass Graph{ constructor(V) { this.V = V; // Rows may not be contiguous this.g = new Array(V + 1); for(let i = 0; i < V + 1; i++) { this.g[i] = new Array(V+1); // Initialize all entries // as false to indicate // that there are // no edges initially for(let j = 0; j < (V + 1); j++) { this.g[i][j] = 0; } } // Initializing node to itself // as it is always reachable for(let i = 1; i <= V; i++) this.g[i][i] = 1; } // Function to add edge between nodes addEdge(v, w) { this.g[v][w] = 1; this.g[w][v] = 1; } // Function to check if nodes are reachable isReachable(s, d) { if (this.g[s][d] == 1) return true; else return false; } // Function to compute the path computePaths() { // Use Floyd Warshall algorithm // to detect if a path exists for(let k = 1; k <= this.V; k++) { // Try every vertex as an // intermediate vertex // to check if a path exists for(let i = 1; i <= this.V; i++) { for(let j = 1; j <= this.V; j++) this.g[i][j] = this.g[i][j] | ((this.g[i][k] != 0 && this.g[k][j] != 0) ? 1 : 0); } } }}// Driver codelet _g = new Graph(4); _g.addEdge(1, 2); _g.addEdge(2, 3); _g.addEdge(1, 4); _g.computePaths(); let u = 4, v = 3; if (_g.isReachable(u, v)) document.write("Yes<br>"); else document.write("No<br>");// This code is contributed by unknown2108</script> |
Output
Yes
Time Complexity: O(V3)
Auxiliary Space: O(V2)
Efficient Solutions
1) We can either use BFS or DFS to find if there is a path from u to v. Below is a BFS-based solution
C++
// C++ program to check if there is exist a path between// two vertices of an undirected graph.#include<bits/stdc++.h>using namespace std;vector<vector<int>> adj;// function to add an edge to graphvoid addEdge(int v,int w){ adj[v].push_back(w); adj[w].push_back(v);}// A BFS based function to check whether d is reachable from s.bool isReachable(int s,int d){ // Base case if(s == d) return true; int n= (int)adj.size(); // Mark all the vertices as not visited vector<bool> visited(n,false); // Create a queue for BFS queue<int> q; // Mark the current node as visited and enqueue it visited[s]= true; q.push(s); while(!q.empty()) { // Dequeue a vertex from queue and print it s=q.front(); q.pop(); // Get all adjacent vertices of the dequeued vertex s // If a adjacent has not been visited, then mark it // visited and enqueue it for(auto x:adj[s]) { // If this adjacent node is the destination node, // then return true if(x == d) return true; // Else, continue to do BFS if(!visited[x]) { visited[x] = true; q.push(x); } } } // If BFS is complete without visiting d return false;}// Driver program to test methods of graph classint main(){ int n = 4; // Create a graph in the above diagram adj = vector<vector<int>>(n); addEdge(0,1); addEdge(0,2); addEdge(1,2); addEdge(2,0); addEdge(2,3); addEdge(3,3); int u = 1, v = 3; if (isReachable(u, v)) cout << "\n There is a path from " << u << " to " << v; else cout << "\n There is no path from " << u << " to " << v; return 0; } |
Java
import java.util.ArrayList;import java.util.LinkedList;import java.util.Queue;// Java program to check if there is exist a path between// two vertices of an undirected graph.public class Graph { // This class represents an undirected graph // using adjacency list representation int V; // No. of vertices // Pointer to an array containing adjacency lists ArrayList<ArrayList<Integer>> adj; Graph(int V){ this.V = V; adj = new ArrayList<>(); for(int i=0;i<V;i++) adj.add(new ArrayList<>()); } // function to add an edge to graph void addEdge(int v, int w) { adj.get(v).add(w); adj.get(w).add(v); } // A BFS based function to check whether d is reachable from s. boolean isReachable(int s, int d) { // Base case if (s == d) return true; // Mark all the vertices as not visited boolean[] visited = new boolean[V]; for (int i = 0; i < V; i++) visited[i] = false; // Create a queue for BFS Queue<Integer> queue = new LinkedList<>(); // Mark the current node as visited and enqueue it visited[s] = true; queue.add(s); while (!queue.isEmpty()) { // Dequeue a vertex from queue and print it s = queue.remove(); // Get all adjacent vertices of the dequeued vertex s // If a adjacent has not been visited, then mark it // visited and enqueue it for (int i=0; i<adj.get(s).size();i++) { // If this adjacent node is the destination node, // then return true if (adj.get(s).get(i) == d) return true; // Else, continue to do BFS if (!visited[adj.get(s).get(i)]) { visited[adj.get(s).get(i)] = true; queue.add(adj.get(s).get(i)); } } } // If BFS is complete without visiting d return false; } // Driver program to test methods of graph class public static void main(String[] args) { // Create a graph given in the above diagram Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); int u = 1, v = 3; if (g.isReachable(u, v)) System.out.println("\n There is a path from "+u+" to "+v); else System.out.println("\n There is no path from "+u+" to "+v); }}// This code is contributed by hritikrommie. |
Python3
# Python3 program to check if there is exist a path between# two vertices of an undirected graph.from collections import dequedef addEdge(v, w): global adj adj[v].append(w) adj[w].append(v)# A BFS based function to check whether d is reachable from s.def isReachable(s, d): # Base case if (s == d): return True # Mark all the vertices as not visited visited = [False for i in range(V)] # Create a queue for BFS queue = deque() # Mark the current node as visited and enqueue it visited[s] = True queue.append(s) while (len(queue) > 0): # Dequeue a vertex from queue and print s = queue.popleft() # queue.pop_front() # Get all adjacent vertices of the dequeued vertex s # If a adjacent has not been visited, then mark it # visited and enqueue it for i in adj[s]: # If this adjacent node is the destination node, # then return true if (i == d): return True # Else, continue to do BFS if (not visited[i]): visited[i] = True queue.append(i) # If BFS is complete without visiting d return False# Driver program to test methods of graph classif __name__ == '__main__': # Create a graph given in the above diagram V = 4 adj = [[] for i in range(V+1)] addEdge(0, 1) addEdge(0, 2) addEdge(1, 2) addEdge(2, 0) addEdge(2, 3) addEdge(3, 3) u,v = 1, 3 if (isReachable(u, v)): print("There is a path from",u,"to",v) else: print("There is no path from",u,"to",v) # This code is contributed by mohit kumar 29. |
C#
using System;using System.Collections.Generic;// C# program to check if there is exist a path between// two vertices of an undirected graph.public class Graph{ // This class represents an undirected graph // using adjacency list representation int V; // No. of vertices // Pointer to an array containing adjacency lists List<List<int>> adj; Graph(int V){ this.V = V; adj = new List<List<int>>(); for(int i = 0; i < V; i++) adj.Add(new List<int>()); } // function to add an edge to graph void addEdge(int v, int w) { adj[v].Add(w); adj[w].Add(v); } // A BFS based function to check whether d is reachable from s. bool isReachable(int s, int d) { // Base case if (s == d) return true; // Mark all the vertices as not visited bool[] visited = new bool[V]; for (int i = 0; i < V; i++) visited[i] = false; // Create a queue for BFS Queue<int> queue = new Queue<int>(); // Mark the current node as visited and enqueue it visited[s] = true; queue.Enqueue(s); while (queue.Count != 0) { // Dequeue a vertex from queue and print it s = queue.Dequeue(); // Get all adjacent vertices of the dequeued vertex s // If a adjacent has not been visited, then mark it // visited and enqueue it for (int i = 0; i < adj[s].Count; i++) { // If this adjacent node is the destination node, // then return true if (adj[s][i] == d) return true; // Else, continue to do BFS if (!visited[adj[s][i]]) { visited[adj[s][i]] = true; queue.Enqueue(adj[s][i]); } } } // If BFS is complete without visiting d return false; } // Driver program to test methods of graph class public static void Main(String[] args) { // Create a graph given in the above diagram Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); int u = 1, v = 3; if (g.isReachable(u, v)) Console.WriteLine("\n There is a path from "+u+" to "+v); else Console.WriteLine("\n There is no path from "+u+" to "+v); }}// This code is contributed by umadevi9616 |
Javascript
<script>// javascript program to check if there is exist a path between// two vertices of an undirected graph. // This class represents an undirected graph // using adjacency list representation var V; // No. of vertices // Pointer to an array containing adjacency lists var adj; V = 4; adj = new Array(); for (var i = 0; i < V; i++) adj.push(new Array()); // function to add an edge to graph function addEdge(v , w) { adj[v].push(w); adj[w].push(v); } // A BFS based function to check whether d is reachable from s. function isReachable(s , d) { // Base case if (s == d) return true; // Mark all the vertices as not visited var visited = new Array(V).fill(false); // Create a queue for BFS var queue = new Array(); // Mark the current node as visited and enqueue it visited[s] = true; queue.push(s); while (queue.length != 0) { // Dequeue a vertex from queue and print it s = queue.pop(); // Get all adjacent vertices of the dequeued vertex s // If a adjacent has not been visited, then mark it // visited and enqueue it for (var i = 0; i < adj[s].length; i++) { // If this adjacent node is the destination node, // then return true if (adj[s][i] == d) return true; // Else, continue to do BFS if (!visited[adj[s][i]]) { visited[adj[s][i]] = true; queue.push(adj[s][i]); } } } // If BFS is complete without visiting d return false; } // Driver program to test methods of graph class // Create a graph given in the above diagram addEdge(0, 1); addEdge(0, 2); addEdge(1, 2); addEdge(2, 0); addEdge(2, 3); addEdge(3, 3); var u = 1, v = 3; if (isReachable(u, v)) document.write("\n There is a path from " + u + " to " + v); else document.write("\n There is no path from " + u + " to " + v);// This code is contributed by gauravrajput1</script> |
Output
There is a path from 1 to 3
Time Complexity: O(V + E)
Auxiliary Space: O(V)
The Recursive Approach
It Basically create a adjacency list then traverse over the source list and the that come under source list
while traversing if we get the destination then we will return true if not then false at the end.
C++
#include<bits/stdc++.h>#include<iostream>using namespace std;vector<vector<int>> graph;void addEdge(int v,int w){ graph[v].push_back(w); graph[w].push_back(v);}bool checkpath(vector<int>adj[],vector<int>&vis,int n,int source,int destination){ if(source==destination)return 1; vis=1; for(auto it:adj){ if(!vis[it]){ bool s=checkpath(adj,vis,n,it,destination); if(s==1)return 1; } } return 0; } bool Path(int n, vector<vector<int>>& edges, int source, int destination) { vector<int>adj[n]; if(source==destination)return 1; for(int i=0;i<edges.size();i++){ adj[edges[i][0]].push_back(edges[i][1]); adj[edges[i][1]].push_back(edges[i][0]); }vector<int>vis(n,0); return checkpath(adj,vis,n,source,destination); }int main(){int n = 4; // Create a graph in the above diagram graph = vector<vector<int>>(n); addEdge(0,1); addEdge(0,2); addEdge(1,2); addEdge(2,0); addEdge(2,3); addEdge(3,3); int u = 1, v = 3; if (Path(n, graph, u, v)) cout << "\n There is a path from " << u << " to " << v; else cout << "\n There is no path from " << u << " to " << v; return 0; } |
Java
// Java code for the above approachimport java.io.*;import java.util.*;class Graph { int V; LinkedList<Integer>[] adj; Graph(int V) { this.V = V; adj = new LinkedList[V]; for (int i = 0; i < V; i++) { adj[i] = new LinkedList<>(); } } void addEdge(int v, int w) { adj[v].add(w); adj[w].add(v); } // Function to check if there is a path between source // and destination boolean checkPath(int source, int destination, boolean[] visited) { // if source and destination are same, return True if (source == destination) { return true; } visited = true; // Iterate through the neighbours of the current // node for (Integer i : adj) { // If the neighbour is not visited yet if (!visited[i]) { if (checkPath(i, destination, visited)) { return true; } } } return false; } boolean Path(int source, int destination) { boolean[] visited = new boolean[V]; return checkPath(source, destination, visited); }}class GFG { public static void main(String[] args) { Graph g = new Graph(4); // Create a graph in the above diagram g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); // Given source and destination int source = 1, destination = 3; // Function call if (g.Path(source, destination)) { System.out.println("There is a path from " + source + " to " + destination); } else { System.out.println("There is no path from " + source + " to " + destination); } }}// This code is contributed by karthik. |
Python3
from collections import defaultdict# Create an empty graphgraph = defaultdict(list)# Function to add edges to the graphdef addEdge(v, w): graph[v].append(w) graph[w].append(v)# Function to check if there is a path between source and destinationdef checkpath(adj, vis, n, source, destination): # if source and destination are same, return True if source == destination: return True vis = 1 # Iterate through the neighbours of the current node for it in adj: # If the neighbour is not visited yet if not vis[it]: s = checkpath(adj, vis, n, it, destination) if s: return True return Falsedef Path(n, edges, source, destination): adj = defaultdict(list) # Create the adjacency list from the edges for i in range(len(edges)): adj[edges[i][0]].append(edges[i][1]) adj[edges[i][1]].append(edges[i][0]) # Initialize the visited array vis = [0]*n # check if there is a path between source and return checkpath(adj, vis, n, source, destination)if __name__ == "__main__": n = 4 # Add edges to the graph addEdge(0, 1) addEdge(0, 2) addEdge(1, 2) addEdge(2, 0) addEdge(2, 3) addEdge(3, 3) # Given source and destination u = 1 v = 3 # Function call if Path(n, graph, u, v): print("There is a path from", u, "to", v) else: print("There is no path from", u, "to", v) # This code is contributed by lokeshpotta20 |
C#
using System;using System.Collections.Generic;class Graph{ int V; LinkedList<int>[] adj; public Graph(int V) { this.V = V; adj = new LinkedList<int>[V]; for (int i = 0; i < V; i++) { adj[i] = new LinkedList<int>(); } } public void addEdge(int v, int w) { adj[v].AddLast(w); adj[w].AddLast(v); } // Function to check if there is a path between source // and destination bool checkPath(int source, int destination, bool[] visited) { // if source and destination are same, return True if (source == destination) { return true; } visited = true; // Iterate through the neighbours of the current node foreach (int i in adj) { // If the neighbour is not visited yet if (!visited[i]) { if (checkPath(i, destination, visited)) { return true; } } } return false; } public bool Path(int source, int destination) { bool[] visited = new bool[V]; return checkPath(source, destination, visited); }}class GFG{ static void Main(string[] args) { Graph g = new Graph(4); // Create a graph in the above diagram g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); // Given source and destination int source = 1, destination = 3; // Function call if (g.Path(source, destination)) { Console.WriteLine("There is a path from " + source + " to " + destination); } else { Console.WriteLine("There is no path from " + source + " to " + destination); } }} |
Javascript
//Javascript code for the above approachconst graph = new Map();function addEdge(v, w) { if (graph.has(v)) { graph.get(v).push(w); } else { graph.set(v, [w]); } if (graph.has(w)) { graph.get(w).push(v); } else { graph.set(w, [v]); }}function checkpath(adj, vis, n, source, destination) { if (source === destination) return 1; vis = 1; for (let i = 0; i < adj.length; i++) { if (!vis[adj[i]]) { let s = checkpath(adj, vis, n, adj[i], destination); if (s === 1) return 1; } } return 0;}function Path(n, edges, source, destination) { if (source === destination) return 1; const adj = new Array(n).fill(0).map(() => []); for (let i = 0; i < edges.length; i++) { adj[edges[i][0]].push(edges[i][1]); adj[edges[i][1]].push(edges[i][0]); } const vis = new Array(n).fill(0); return checkpath(adj, vis, n, source, destination);}//Driver codeconst n = 4;addEdge(0, 1);addEdge(0, 2);addEdge(1, 2);addEdge(2, 0);addEdge(2, 3);addEdge(3, 3);const u = 1, v = 3;if (Path(n, graph, u, v)) { document.write("There is a path from " + u + " to " + v);} else { document.write("There is no path from " + u + " to " + v);} |
Output
There is a path from 1 to 3
Below is the DFS-based solution
C++
// C++ program to check if there is exist a path between// two vertices of an undirected graph.#include<bits/stdc++.h>using namespace std;vector<vector<int>> graph;void addEdge(int v,int w){ graph[v].push_back(w); graph[w].push_back(v);} bool dfs(vector<int> adj[], vector<int> &vis, int start, int end); bool validPath(int n, vector<vector<int>>& edges, int start, int end); bool validPath(int n, vector<vector<int>>& edges, int start, int end) { vector<int> adj[n]; for(int i=0; i<edges.size(); i++){ int u = edges[i][0]; int v = edges[i][1]; adj[u].push_back(v); adj[v].push_back(u); } vector <int> vis(n, 0); for(int i=0; i<n; i++) if(vis[i] == 0) if(dfs(adj, vis, start, end)) return true; return false; } bool dfs(vector<int> adj[], vector<int> &vis, int start, int end){ if(end == start) return true; vis[start] = 1; for(auto it: adj[start]) if(vis[it]==0) if(dfs(adj, vis, it, end)) return true; return false; }int main(){ int n = 4; // Create a graph in the above diagram graph = vector<vector<int>>(n); addEdge(0,1); addEdge(0,2); addEdge(1,2); addEdge(2,0); addEdge(2,3); addEdge(3,3); int u = 1, v = 3; if (validPath(n, graph, u, v)) cout << "\n There is a path from " << u << " to " << v; else cout << "\n There is no path from " << u << " to " << v; return 0; } |
Java
import java.util.ArrayList;public class CheckPathInUndirectedGraph { // Define a graph using an ArrayList of ArrayLists of Integers static ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); // Function to add an undirected edge between two vertices static void addEdge(int v, int w) { graph.get(v).add(w); graph.get(w).add(v); } // Function to perform DFS traversal on the graph static boolean dfs(ArrayList<Integer>[] adj, ArrayList<Integer> vis, int start, int end) { // If the end vertex is reached, return true if (end == start) { return true; } // Mark the current vertex as visited vis.set(start, 1); // Traverse the adjacent vertices of the current vertex for (int it : adj[start]) { // If the adjacent vertex has not been visited, // recursively call the dfs function if (vis.get(it) == 0) { if (dfs(adj, vis, it, end)) { return true; } } } // If there is no path between the vertices, return false return false; } // Function to check if a path exists between two vertices static boolean validPath(int n, int[][] edges, int start, int end) { // Create the adjacency list representation of the graph ArrayList<Integer>[] adj = new ArrayList[n]; for (int i = 0; i < n; i++) { adj[i] = new ArrayList<Integer>(); } for (int i = 0; i < edges.length; i++) { int u = edges[i][0]; int v = edges[i][1]; adj[u].add(v); adj[v].add(u); } // Create an array to mark visited vertices ArrayList<Integer> vis = new ArrayList<>(n); for (int i = 0; i < n; i++) { vis.add(0); } // Traverse the graph using DFS and return true if a path is found between the vertices for (int i = 0; i < n; i++) { if (vis.get(i) == 0) { if (dfs(adj, vis, start, end)) { return true; } } } // If there is no path between the vertices, return false return false; } // Main function to test the code public static void main(String[] args) { int n = 4; // Initialize the graph with empty ArrayLists for (int i = 0; i < n; i++) { graph.add(new ArrayList<>()); } // Add the edges to the graph addEdge(0, 1); addEdge(0, 2); addEdge(1, 2); addEdge(2, 0); addEdge(2, 3); addEdge(3, 3); int u = 1, v = 3; // Check if there is a path between u and v if (validPath(n, new int[][]{{0,1},{0,2},{1,2},{2,0},{2,3},{3,3}}, u, v)) { System.out.println("There is a path from " + u + " to " + v); } else { System.out.println("There is no path from " + u + " to " + v); } }} |
Python3
# Python program for the above approach:graph = []def addEdge(v, w): global graph graph[v].append(w) graph[w].append(v)def dfs(adj, vis, start, end): if(end == start): return True vis[start] = 1; for it in adj[start]: if(vis[it]==0): if(dfs(adj, vis, it, end)): return True return Falsedef validPath(n, edges, start, end): adj = [[] for _ in range(n)] for i in range(len(edges)): u = edges[i][0] v = edges[i][1] adj[u].append(v) adj[v].append(u) vis = [0]*n for i in range(n): if(vis[i] == 0): if(dfs(adj, vis, start, end)): return True return False## Driver coden = 4## Create a graph in the above diagramgraph = [[] for _ in range(n)];addEdge(0,1)addEdge(0,2)addEdge(1,2)addEdge(2,0)addEdge(2,3)addEdge(3,3)u = 1v = 3if (validPath(n, graph, u, v)): print("There is a path from", u, "to", v)else: print("There is no path from", u, "to", v) # This code is contributed by subhamgoyal2014. |
C#
// C# program to check if there is exist a path between// two vertices of an undirected graph.using System;using System.Collections.Generic;class Graph { List<List<int>> adj; public Graph(int n) { adj = new List<List<int>>(n); for(int i=0; i<n; i++) adj.Add(new List<int>()); } // Function to add an undirected edge between two vertices public void AddEdge(int v, int w) { adj[v].Add(w); adj[w].Add(v); } // Function to perform DFS traversal on the graph bool dfs(List<int>[] adj, int[] vis, int start, int end) { // If the end vertex is reached, return true if (end == start) return true; vis[start] = 1; foreach (int i in adj[start]) if (vis[i] == 0) if (dfs(adj, vis, i, end)) return true; return false; } // Function to check if a path exists between two vertices public bool ValidPath(int start, int end) { int n = adj.Count; int[] vis = new int[n]; for(int i=0; i<n; i++) vis[i] = 0; for(int i=0; i<n; i++) if (vis[i] == 0) if (dfs(adj.ToArray(), vis, start, end)) return true; return false; }}public class Gfg { public static void Main() { int n = 4; Graph graph = new Graph(n); graph.AddEdge(0, 1); graph.AddEdge(0, 2); graph.AddEdge(1, 2); graph.AddEdge(2, 0); graph.AddEdge(2, 3); graph.AddEdge(3, 3); int u = 1, v = 3; if (graph.ValidPath(u, v)) Console.WriteLine("\n There is a path from " + u + " to " + v); else Console.WriteLine("\n There is no path from " + u + " to " + v); }} |
Javascript
let graph = [];function addEdge(v, w) { graph[v].push(w); graph[w].push(v);}function dfs(adj, vis, start, end) { if (end === start) { return true; } vis[start] = 1; for (let i = 0; i < adj[start].length; i++) { let it = adj[start][i]; if (vis[it] === 0) { if (dfs(adj, vis, it, end)) { return true; } } } return false;}function validPath(n, edges, start, end) { let adj = new Array(n); for (let i = 0; i < n; i++) { adj[i] = []; } for (let i = 0; i < edges.length; i++) { let u = edges[i][0]; let v = edges[i][1]; adj[u].push(v); adj[v].push(u); } let vis = new Array(n).fill(0); for (let i = 0; i < n; i++) { if (vis[i] === 0) { if (dfs(adj, vis, start, end)) { return true; } } } return false;}let n = 4;graph = new Array(n);for (let i = 0; i < n; i++) { graph[i] = [];}addEdge(0, 1);addEdge(0, 2);addEdge(1, 2);addEdge(2, 0);addEdge(2, 3);addEdge(3, 3);let u = 1, v = 3;if (validPath(n, graph, u, v)) { console.log(`There is a path from ${u} to ${v}`);} else { console.log(`There is no path from ${u} to ${v}`);} |
Output
There is a path from 1 to 3
2) We can use disjoint-set data structure (also called union find) to find there is a path from vertex u to vertex v.
C++
#include <bits/stdc++.h>#include <iostream>using namespace std;vector<vector<int> > graph;void addEdge(int v, int w){ graph[v].push_back(w); graph[w].push_back(v);}class UnionFind { vector<int> parent, rank;public: UnionFind(int n) : parent(n), rank(n, 1) { iota(parent.begin(), parent.end(), 0); } // Function to find the parent of vertex int find(int x) { if (x != parent[x]) { parent[x] = find(parent[x]); } return parent[x]; } // Function to unite the vertices void unite(int x, int y) { int parentX = find(x), parentY = find(y); // If both vertices does not belong to same set, unite them if (parentX != parentY) { if (rank[parentX] > rank[parentY]) { swap(parentX, parentY); } // Modify the parent of the smaller group as the // parent of the larger group, also increment // the size of the larger group. parent[parentX] = parentY; rank[parentY] += rank[parentX]; } }};bool validPath(int n, vector<vector<int> >& adj, int source, int destination){ UnionFind uf(n); for (int i = 0; i < n; i++) { int u = i; for (auto v : adj[i]) { uf.unite(u, v); } } return uf.find(source) == uf.find(destination);}int main(){ int n = 4; // Create a graph in the above diagram graph = vector<vector<int> >(n); addEdge(0, 1); addEdge(0, 2); addEdge(1, 2); addEdge(2, 0); addEdge(2, 3); addEdge(3, 3); int u = 1, v = 3; if (validPath(n, graph, u, v)) cout << "There is a path from " << u << " to " << v << endl; else cout << "There is no path from " << u << " to " << v << endl; return 0;} |
Java
import java.util.*;class Graph { List<List<Integer> > adjList; public Graph(int n) { adjList = new ArrayList<>(); for (int i = 0; i < n; i++) { adjList.add(new ArrayList<>()); } } public void addEdge(int v, int w) { adjList.get(v).add(w); adjList.get(w).add(v); }}class UnionFind { int[] parent; int[] rank; public UnionFind(int n) { parent = new int[n]; rank = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 1; } } // Function to find the parent of vertex public int find(int x) { if (x != parent[x]) { parent[x] = find(parent[x]); } return parent[x]; } // Function to unite the vertices public void unite(int x, int y) { int parentX = find(x), parentY = find(y); // If both vertices does not belong to same set, unite them if (parentX != parentY) { if (rank[parentX] > rank[parentY]) { int temp = parentX; parentX = parentY; parentY = temp; } // Modify the parent of the smaller group as the // parent of the larger group, also increment // the size of the larger group. parent[parentX] = parentY; rank[parentY] += rank[parentX]; } }}class Main { public static boolean validPath(int n, Graph graph, int source, int destination) { UnionFind uf = new UnionFind(n); for (int i = 0; i < n; i++) { int u = i; for (int v : graph.adjList.get(i)) { uf.unite(u, v); } } return uf.find(source) == uf.find(destination); } public static void main(String[] args) { int n = 4; // Create a graph in the above diagram Graph graph = new Graph(n); graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 2); graph.addEdge(2, 0); graph.addEdge(2, 3); graph.addEdge(3, 3); int u = 1, v = 3; if (validPath(n, graph, u, v)) { System.out.println("There is a path from " + u + " to " + v); } else { System.out.println("There is no path from " + u + " to " + v); } }}// This code is contributed By Prajwal Kandekar |
Python3
from typing import Listgraph = []def addEdge(v: int, w: int) -> None: graph[v].append(w) graph[w].append(v)class UnionFind: def __init__(self, n: int) -> None: self.parent = list(range(n)) self.rank = [1] * n # Function to find the parent of vertex def find(self, x: int) -> int: if x != self.parent[x]: self.parent[x] = self.find(self.parent[x]) return self.parent[x] # Function to unite the vertices def unite(self, x: int, y: int) -> None: parentX, parentY = self.find(x), self.find(y) # If both vertices does not belong to same set, unite them if parentX != parentY: if self.rank[parentX] > self.rank[parentY]: parentX, parentY = parentY, parentX # Modify the parent of the smaller group as the # parent of the larger group, also increment # the size of the larger group. self.parent[parentX] = parentY self.rank[parentY] += self.rank[parentX]def validPath(n: int, adj: List[List[int]], source: int, destination: int) -> bool: uf = UnionFind(n) for i in range(n): u = i for v in adj[i]: uf.unite(u, v) return uf.find(source) == uf.find(destination)if __name__ == '__main__': n = 4 # Create a graph in the above diagram graph = [[] for i in range(n)] addEdge(0, 1) addEdge(0, 2) addEdge(1, 2) addEdge(2, 0) addEdge(2, 3) addEdge(3, 3) u, v = 1, 3 if validPath(n, graph, u, v): print(f"There is a path from {u} to {v}") else: print(f"There is no path from {u} to {v}") |
Javascript
// Define an empty array for the graphlet graph = [];// Function to add edges to the graphfunction addEdge(v, w) { graph[v].push(w); graph[w].push(v);}// Define the UnionFind classclass UnionFind { constructor(n) { this.parent = [...Array(n).keys()]; this.rank = Array(n).fill(1); } // Function to find the parent of a vertex find(x) { if (x != this.parent[x]) { this.parent[x] = this.find(this.parent[x]); } return this.parent[x]; } // Function to unite two vertices unite(x, y) { let parentX = this.find(x); let parentY = this.find(y); // If both vertices do not belong to the same set, unite them if (parentX != parentY) { if (this.rank[parentX] > this.rank[parentY]) { [parentX, parentY] = [parentY, parentX]; } // Modify the parent of the smaller group as the // parent of the larger group, also increment // the size of the larger group. this.parent[parentX] = parentY; this.rank[parentY] += this.rank[parentX]; } }}// Function to check if a valid path exists between two verticesfunction validPath(n, adj, source, destination) { let uf = new UnionFind(n); for (let i = 0; i < n; i++) { let u = i; for (let v of adj[i]) { uf.unite(u, v); } } return uf.find(source) == uf.find(destination);}// Main function to test the algorithmif (require.main === module) { const n = 4; // Create a graph in the above diagram graph = [...Array(n)].map(() => []); addEdge(0, 1); addEdge(0, 2); addEdge(1, 2); addEdge(2, 0); addEdge(2, 3); addEdge(3, 3); const u = 1; const v = 3; if (validPath(n, graph, u, v)) { console.log(`There is a path from ${u} to ${v}`); } else { console.log(`There is no path from ${u} to ${v}`); }} |
C#
using System;using System.Collections.Generic;using System.Linq;class Program{ static List<List<int>> graph; static void Main() { int n = 4; // Create a graph in the above diagram graph = new List<List<int>>(n); for (int i = 0; i < n; i++) { graph.Add(new List<int>()); } AddEdge(0, 1); AddEdge(0, 2); AddEdge(1, 2); AddEdge(2, 0); AddEdge(2, 3); AddEdge(3, 3); int u = 1, v = 3; if (ValidPath(n, graph, u, v)) Console.WriteLine($"There is a path from {u} to {v}"); else Console.WriteLine($"There is no path from {u} to {v}"); Console.ReadLine(); } static void AddEdge(int v, int w) { graph[v].Add(w); graph[w].Add(v); } class UnionFind { List<int> parent, rank; public UnionFind(int n) { parent = Enumerable.Range(0, n).ToList(); rank = Enumerable.Repeat(1, n).ToList(); } // Function to find the parent of vertex public int Find(int x) { if (x != parent[x]) { parent[x] = Find(parent[x]); } return parent[x]; } // Function to unite the vertices public void Unite(int x, int y) { int parentX = Find(x), parentY = Find(y); // If both vertices does not belong to same set, unite them if (parentX != parentY) { if (rank[parentX] > rank[parentY]) { Swap(ref parentX, ref parentY); } // Modify the parent of the smaller group as the // parent of the larger group, also increment // the size of the larger group. parent[parentX] = parentY; rank[parentY] += rank[parentX]; } } private void Swap<T>(ref T x, ref T y) { T temp = x; x = y; y = temp; } } static bool ValidPath(int n, List<List<int>> adj, int source, int destination) { UnionFind uf = new UnionFind(n); for (int i = 0; i < n; i++) { int u = i; foreach (int v in adj[i]) { uf.Unite(u, v); } } return uf.Find(source) == uf.Find(destination); }} |
Output
There is a path from 1 to 3
Time Complexity: O( E * ? ( V ) ) where ? is the Inverse Ackermann Function.
Auxiliary Space: O( V )
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
