Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Question
3.
BFS Algorithm 
3.1.
Implementation: cpp
3.2.
Output
3.3.
Complexity Analysis:  
4.
DFS Algorithm
4.1.
Implementation: cpp
4.2.
Complexity Analysis:  
4.3.
Trade-offs between BFS and DFS: 
5.
Frequently Asked Questions
5.1.
Is there a path in the directed graph?
5.2.
How do you find all possible paths in a directed graph?
5.3.
How do you find the number of paths between two vertices?
5.4.
What is graph with a path between every pair of vertices called?
5.5.
How can a directed graph's connectivity be determined?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Check if there is a Path between Two Vertices in a Directed Graph

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

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.

 

example of graph example

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.
Time Complexity
  • The Complexity of Space: O (V).

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

Space complexity

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 ComplexityO(V+E), where V is the number of graph vertices, and E is the number of graph edges.
Time Complexity
  • The Complexity of SpaceO (V).

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

Space complexity

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.

Recommended Problems:

Recommended Readings:

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!

Happy learning!

Previous article
Check whether given degrees of vertices represent a Graph or Tree
Next article
Parallel Courses III
Live masterclass