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

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;
}

You can also try this code with Online C++ Compiler

Run Code

Output

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

You can also try this code with Online C++ Compiler

Run Code

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;
}

You can also try this code with Online C++ Compiler

Run Code

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.

Recommended Problems:

• Unique Paths
• Longest Path Directed Acyclic Graph
• Longest Path In A Tree
   

Recommended Readings:

• Detect cycle in directed graph
   

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!