Find if there is a path between two vertices in a directed graph

In computer science and graph theory, solutions to various real-life model scenarios rely heavily on directed graphs. These specialized graphs consist of vertices connected by directed edges pointing to other vertices. Determining whether a path exists between two specified points is a typical difficult problem using directed graphs. In this article, we'll explore various ways to solve this dilemma using C, including the syntax required for each process to ensure things are easy to understand. Additionally, we will detail the algorithms that illustrate each method and include two executable code examples.

grammar

Before diving into the specific details, it is crucial to understand the language structure that underpins the methodology here. So, before moving on to the code example, let's first check this syntax.

bool isPathExists(int startVertex, int endVertex, const vector<vector<int>>& graph);

algorithm

Finding a path between two vertices in a directed graph can be solved using a variety of techniques. This article will focus on two widely used methods −

Method 1: Depth First Search (DFS)

• Create a visited array to track visited vertices during the traversal.

• Initialize all elements of the visited array to false.

• Mark startVertex as visited.

• If the start vertex and the end vertex are the same, return true, indicating that there is a path.

• For each adjacent vertex of the current vertex, use the adjacent vertex as the new starting vertex and call the isPathExists function recursively.

• Returns true if any recursive call returns true.

• If no recursive call returns true, return false.

Method 2: Breadth First Search (BFS)

• Create a visited array to track visited vertices during the traversal.

• Initialize all elements of the visited array to false.

• Create a queue to store pending vertices.

• Add startVertex to the queue and mark it as visited.

• If the queue is not empty, perform the following operations:

• Dequeue a vertex from the queue.

• If the dequeued vertex is the same as endVertex, it returns true, indicating that there is a path.

• For each vertex adjacent to the dequeued vertex, if it has not been visited, enqueue it and mark it as visited.

• Returns false if the queue becomes empty and no path is found.

Example 1: Depth First Search (DFS) Method

#include <iostream>
#include <vector>
using namespace std;

bool isPathExists(int startVertex, int endVertex, const vector<vector<int>>& graph) {
   vector<bool> visited(graph.size(), false);
   visited[startVertex] = true;
  
   if (startVertex == endVertex)
      return true;
  
   for (int adjVertex : graph[startVertex]) {
      if (!visited[adjVertex] && isPathExists(adjVertex, endVertex, graph))
         return true;
   }
  
   return false;
}

int main() {
   // Example usage
   int numVertices = 6;
   vector<vector<int>> graph(numVertices);
   graph[0] = {1, 2};
   graph[1] = {3};
   graph[2] = {1};
   graph[3] = {4, 5};
   graph[4] = {};
   graph[5] = {4};

   int startVertex = 0;
   int endVertex = 5;

   if (isPathExists(startVertex, endVertex, graph))
      cout << "A path exists between " << startVertex << " and " << endVertex << endl;
   else
      cout << "No path exists between " << startVertex << " and " << endVertex << endl;

   return 0;
}

Output

A path exists between 0 and 5

The code starts by defining a function called isPathExists, which accepts startVertex, endVertex, and a graph represented by an adjacency list as parameters. It initializes a boolean vector called visited that keeps track of visited vertices. While executing this function, it first checks if startVertex and endVertex are same by comparing them.

When these vertices completely coincide in this context, the function returns true immediately.

If this is not the case, and they are distinct from each other, another action will be taken to check the adjacency between them to determine if a path exists between them.

This process involves repeatedly iterating the adjacent vertices of the starting vertex; each iteration will use the newly searched vertex as the new starting point, and continue to find available paths by recursively calling "isPathExists". This cycle repeats until all possible paths are exhausted or a successful path is found.

If any of these repeated calls detect a potential edge connecting the start node and the end node, then the output of this filtering will mean that there is indeed a usable interconnection between these two nodes. Therefore, True will be returned immediately.

Otherwise, when the complexity set in the algorithm results in no available route, a fail-safe loop action will be initiated. In the event of such an outcome, it returns False, regretting that the connection between the nodes failed.

Example 2: Breadth First Search (BFS) method

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool isPathExists(int startVertex, int endVertex, const vector<vector<int>>& graph) {
   vector<bool> visited(graph.size(), false);
   visited[startVertex] = true;
  
   queue<int> verticesQueue;
   verticesQueue.push(startVertex);
  
   while (!verticesQueue.empty()) {
      int currVertex = verticesQueue.front();
      verticesQueue.pop();
  
      if (currVertex == endVertex)
         return true;
  
      for (int adjVertex : graph[currVertex]) {
         if (!visited[adjVertex]) {
            visited[adjVertex] = true;
            verticesQueue.push(adjVertex);
         }
      }
   }
  
   return false;
}

int main() {
   // Example usage
   int numVertices = 6;
   vector<vector<int>> graph(numVertices);
   graph[0] = {1, 2};
   graph[1] = {3};
   graph[2] = {1};
   graph[3] = {4, 5};
   graph[4] = {};
   graph[5] = {4};

   int startVertex = 0;
   int endVertex = 5;

   if (isPathExists(startVertex, endVertex, graph))
      cout << "A path exists between " << startVertex << " and " << endVertex << endl;
   else
      cout << "No path exists between " << startVertex << " and " << endVertex << endl;

   return 0;
}

Output

A path exists between 0 and 5

This code defines an isPathExists function, which accepts startVertex, endVertex and the graph represented by the adjacency list as parameters. It initializes a boolean vector called visited to keep track of visited vertices, and a queue called verticesQueue to store pending vertices.

This function starts by enqueuing startVertex and marking it as visited. The operation of our algorithm begins by entering an iterative loop that continues as long as there are items in its processing queue structure. As this structured iteration proceeds, two checks are performed each cycle: first verifying that the current iteration's dequeued vertex matches the target endpoint specified in the previous execution; if the two successfully match, return 'true' otherwise Continue to the next step, which is to explore nearby outlying points. During this exploration process, any adjacent unexplored vertices are marked as 'visited' before being put into the queue for deeper iteration and testing to see if they match endVertex.

After all exploration and verification are successful, if there is nothing added to the queue, the function will return false.

in conclusion

In the development of computer science, the complexity of navigating directed graphs may pose a fundamental problem. To mitigate these challenges, one of our goals is to explore two common approaches implemented in C. Depth-first search (DFS) and breadth-first search (BFS) are at the forefront of these techniques, and they provide step-by-step procedures and working code examples that demonstrate each algorithm. Once mastered, these methods unlock new potential when dealing with path-finding obstacles in multiple settings (such as routing networks or analyzing social connectivity frameworks) and serve as valuable starting points in the enhancement development phase.

The above is the detailed content of Find if there is a path between two vertices in a directed graph. For more information, please follow other related articles on the PHP Chinese website!