Trouver s'il existe un chemin entre deux sommets dans un graphe orienté

在计算机科学和图论中，解决各种现实生活模型场景的方案严重依赖于有向图。这些专门的图由通过指向其他顶点的有向边连接的顶点组成。确定两个指定点之间是否存在路径是使用有向图的一个典型难题。在本文中，我们将探讨使用C++解决这个困境的各种方法，包括每个过程所需的语法，以确保事情易于理解。此外，我们将详细介绍精心说明每种方法的算法，并包含两个可执行的代码示例。

语法

在深入了解具体细节之前，理解支撑这里方法论的语言结构是至关重要的。因此，在继续查看代码示例之前，让我们首先检查这个语法。

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

算法

在有向图中找到两个顶点之间的路径可以使用多种技术来解决。本文将重点讨论两种广泛使用的方法−

方法一：深度优先搜索（DFS）

• 创建一个visited数组来在遍历过程中跟踪已访问的顶点。

• 将visited数组的所有元素初始化为false。

• 将startVertex标记为已访问。

• 如果起始顶点与结束顶点相同，则返回true，表示存在一条路径。

• 对于当前顶点的每个相邻顶点，以相邻顶点作为新的起始顶点，递归调用isPathExists函数。

• 如果任何递归调用返回true，则返回true。

• 如果没有递归调用返回true，则返回false。

方法二：广度优先搜索（BFS）

• 创建一个visited数组来在遍历过程中跟踪已访问的顶点。

• 将visited数组的所有元素初始化为false。

• 创建一个队列来存储待处理的顶点。

• 将startVertex加入队列，并标记为已访问。

• 如果队列不为空，执行以下操作：

• 从队列中出队一个顶点。

• 如果出队的顶点与endVertex相同，则返回true，表示存在一条路径。

• 对于每个被出队的顶点的相邻顶点，如果它尚未被访问，则将其入队并标记为已访问。

• 如果队列变为空并且没有找到路径，则返回 false。

示例1：深度优先搜索（DFS）方法

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

输出

A path exists between 0 and 5

代码从定义一个名为isPathExists的函数开始，该函数接受startVertex、endVertex和以邻接表表示的图作为参数。它初始化了一个名为visited的布尔向量，用于跟踪已访问的顶点。在执行此函数时，它首先通过比较它们来检查startVertex和endVertex是否相同。

当这些顶点在此上下文中完全重合时，函数立即返回true。

如果情况不是这样的，并且它们彼此不同，将采取另一种行动来检查它们之间的邻接性，以确定它们之间是否存在路径。

这个过程涉及反复迭代起始顶点的相邻顶点；每次迭代都会使用新搜索到的顶点作为新的起始点，通过递归调用“isPathExists”来继续寻找可用路径。这个循环会重复进行，直到所有可能的路径耗尽或者找到一条成功的路径。

如果这些重复调用中的任何一个检测到连接起始节点和结束节点的潜在边缘，那么这种筛选的输出将意味着这两个节点之间确实存在可用的互连。因此，将立即返回True。

否则，当算法中设置的复杂度导致不存在可用路由时，将启动故障安全的循环动作。在出现这种结果时，它返回False，对节点之间的连接失败表示遗憾。

示例2：广度优先搜索（BFS）方法

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

输出

A path exists between 0 and 5

该代码定义了一个isPathExists函数，该函数接受startVertex、endVertex和以邻接表表示的图作为参数。它初始化了一个名为visited的布尔向量来跟踪访问过的顶点，并初始化了一个名为verticesQueue的队列来存储待处理的顶点。

该函数从将startVertex入队并标记为已访问开始。我们的算法的运行始于进入一个迭代循环，只要其处理队列结构中仍有项目存在，该循环就会持续进行。随着这个结构化的重复的进行，每个周期执行两个检查：首先验证当前迭代的出队顶点是否与之前执行中指定的目标终点匹配；如果两者成功匹配，则返回'true'，否则继续下一步，即探索附近的外围点。在这个探索过程中，任何相邻的未探索顶点在放入队列进行更深层次的迭代检查之前都会被标记为'visited'，并测试它们是否与endVertex匹配。

Une fois toutes les explorations et vérifications réussies, si rien n'est ajouté à la file d'attente, la fonction retournera false.

Conclusion

Dans le développement de l'informatique, la complexité de la navigation dans les graphiques orientés peut poser un problème fondamental. Pour atténuer ces défis, l'un de nos objectifs est d'explorer deux approches courantes mises en œuvre en utilisant C++. La recherche en profondeur d'abord (DFS) et la recherche en largeur d'abord (BFS) sont à la pointe de ces techniques et fournissent des procédures étape par étape et des exemples de code de travail qui démontrent chaque algorithme. Une fois maîtrisées, ces méthodes libèrent un nouveau potentiel lorsqu'il s'agit de surmonter des obstacles à la recherche de chemin dans de multiples contextes (tels que le routage des réseaux ou l'analyse des cadres de connectivité sociale) et servent de points de départ précieux dans la phase de développement de l'amélioration.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!