Welcome, Ninjas! We're back with a fresh data structure challenge: determine whether a path may connect a directed graph's vertex pairs. The problem statement will be presented here first, followed by the approach and implementation in cpp with different approaches.

Let's discuss the problem statement that will clear up any questions regarding a graph.

Question

Verify if a path connects the first given vertex to the second given vertex in a Directed Graph with two vertices.

Consider the following Graph:
In the graph below, for instance, there are two possible routes from vertex 0 to vertex 7: [0â€”3â€”4â€”6â€”7] and [0â€”3â€”5â€”6â€”7]. On the other hand, the path from vertex 7 to any other vertex is impossible.

Either a breadth-first search (BFS) or a depth-first search (DFS) can be used to find a path between two vertices (BFS). In BFS (or DFS), use the first vertex as a source and proceed as usual (or DFS). Return true if our traverse finds the second vertex; otherwise, return false.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

BFS Algorithm

BFS is utilized in the implementation below.

Create a queue and a visited array of size V, where V is the number of vertices, and the variety is initially filled with 0.

Push u into the queue and mark u as visited to add the starting node.

Repeat the loop as long as the queue is not empty.

Dequeue the queue's first entry. Repeat all of its surrounding components. Return true if any of the nearby features is the destination. Place all of the neighbouring, unvisited vertices in the queue and mark them as visited.

Due to BFS, the destination cannot be reached, returning false.

Implementation: cpp

//A graph path between two vertices can be checked using a C++ //application.
#include<iostream>
#include <list>
using namespace std;
// This class uses an adjacency list to represent a directed graph.
class Graph
{
int E; // No. of vertices
list<int> *adjac; //Contains a pointer to an array of adjacency lists.
public:
Graph(int E); // Constructor
void Edge(int v, int w); //graphing function to add edges
bool Reachable(int s, int d);
};
Graph::Graph(int E)
{
this->E = E;
adjac = new list<int>[E];
}
void Graph::Edge(int v, int w)
{
adjac[v].push_back(w); // Add w to v's list.
}
// A BFS-based function to check whether d is reachable from s.
bool Graph::Reachable(int s, int d)
{
// Base case
if (s == d)
return true;
// Mark all the vertices as not visited
bool *vst = new bool[E];
for (int i = 0; i < E; i++)
vst[i] = false;
// Create a queue for BFS
list<int> que;
// Enqueue the current node and mark it as visited.
vst[s] = true;
que.push_back(s);
// It will obtain all of a vertex's surrounding vertices.
list<int>::iterator ind;
while (!que.empty())
{
// Take a vertex out of the queue and print it.
s = que.front();
que.pop_front();
// Get every vertex that is close to the dequeued vertex s. //If an adjacent hasn't been visited, mark it as visited and add it to //the queue.
for (ind = adjac[s].begin(); ind != adjac[s].end(); ++ind)
{
// Return true if this nearby node is the destination node.
if (*ind == d)
return true;
// Else, continue to do BFS
if (!vst[*ind])
{
vst[*ind] = true;
que.push_back(*ind);
}
}
}
// If BFS can be completed without going to d
return false;
}
// Driver application to test graph class method
int main()
{
// Make the graph shown in the illustration above.
Graph grap(4);
grap.Edge(0, 2);
grap.Edge(0, 1);
grap.Edge(2, 0);
grap.Edge(1, 2);
grap.Edge(2, 3);
grap.Edge(3, 3);
int u_new = 1, v_new = 3;
if(grap.Reachable(u_new, v_new))
cout<< "A path exists from " << u_new << " to " << v_new;
else
cout<< "\n No path exists from " << u_new << " to " << v_new;
u_new = 3, v_new = 1;
if(grap.Reachable(u_new, v_new))
cout<< "\n A path exists from " << u_new << " to " << v_new;
else
cout<< "\n No path exists from " << u_new << " to " << v_new;
return 0;
}

Output

A path exists from 1 to 3
No path exists from 3 to 1

Complexity Analysis:

Time Complexity: O(V+E), where V is the number of graph vertices, and E is the number of graph edges, is the time complexity of the problem.

The Complexity of Space:O (V).

The queue can contain a maximum of V elements. So, O is the required space (V).

DFS Algorithm

Return 1 if start==end because we must arrive at our destination.

Mark the first visit.

Explore the directly linked start vertices, iterating the DFS Algorithm function for each new vertex.

If we fail to arrive at our goal, return 0.

Implementation: cpp

#include <bits/stdc++.h>
using namespace std;
vector < long long > adjac[100000];
bool vst[100000];
bool dfs(int src, int node) {
if (src == node)
return true;
vst[src] = 1;
for (auto x: adjac[src]) {
if (!vst[x])
if (dfs(x, node))
return true;
}
return false;
}
int main() {
int V = 4;
vector < long long > arr = {
2,
5,
7,
9
};
int E = 4;
vector < pair < long long, long long > > paired = {
{
7,
2
},
{
9,
5
},
{
7,
9
},
{
2,
9
}
};
//arr doesnt actually matter but in large test cases you can store //arr and pairing
for (int i = 0; i < E; i++)
adjac[paired[i].first].push_back(paired[i].second);
int sender = 7, receiver = 9;
if (dfs(sender, receiver))
cout << "1";
else
cout << "0";
return 0;
}

Complexity Analysis:

Time Complexity: O(V+E), where V is the number of graph vertices, and E is the number of graph edges.

The Complexity of Space: O (V).

The stack can have a maximum of V components. So, O is the required space (V).

Trade-offs between BFS and DFS:

The shortest path between nodes can be found using a breadth-first search, but a depth-first search may travel extremely far through one nearby node before ever reaching its neighbors.

Frequently Asked Questions

Is there a path in the directed graph?

In a directed graph, a required route (also known as a dipath) is a finite or infinite sequence of edges that connects a series of unique vertices with the additional requirement that the edges all point in the same direction.

How do you find all possible paths in a directed graph?

Using exponential, find every potential path through any graph. Backtracking can be used to fix the problem. We can use Depth First Search for DAGs (DFS). Start from any node in the DFS code, travel to the furthest dead end, and use an array or list to record all the nodes you visited along the way.

How do you find the number of paths between two vertices?

Create a recursive function using a graph's destination and node indexes as inputs. To store the count, keep a global or static variable called count. To locate alternate routes, mark the current node as unvisited when returning and use a visited array to maintain track of the nodes that have been visited.

What is graph with a path between every pair of vertices called?

A graph is said to be connected if a path connects each vertex pair. There should be a path connecting each vertex to every other vertex. That is referred to as a graph's connectedness. A graph is considered disconnected if it has numerous disconnected edges and vertices.

How can a directed graph's connectivity be determined?

Determine whether a directed graph is highly linked or not. If every vertex in a directed graph can be reached from every other vertex, the graph is said to be highly connected. Conducting a Depth-first search (DFS) or a Breadth-first search (BFS) beginning at each graph vertex is a straightforward solution.

Conclusion

Finally, you have reached the article's conclusion. Congratulations!! You gained knowledge of the Check if there is a path between two vertices in a directed graph in this blog.

Are you eager to read more articles on Graph questions for Interview? Coding Ninjas cover you, so don't worry. View more topics on Coding ninjas.

Please refer to our guided pathways on Code studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.

Please do upvote our blogs if you find them helpful and informative!