在有向图中找到两个顶点之间是否存在路径

在计算机科学和图论中，解决各种现实生活模型场景的方案严重依赖于有向图。这些专门的图由通过指向其他顶点的有向边连接的顶点组成。确定两个指定点之间是否存在路径是使用有向图的一个典型难题。在本文中，我们将探讨使用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匹配。

在所有的探索和验证都成功之后，如果队列中没有任何添加，该函数将返回false。

结论

在计算机科学的发展中，导航有向图的复杂性可能会构成一个基本问题。为了减轻这些挑战，我们的目标之一是探索使用C++实现的两种常见方法。深度优先搜索（DFS）和广度优先搜索（BFS）是这些技术的前沿，它们提供了逐步演示每个算法的过程和工作代码示例。一旦掌握了这些方法，就可以在处理多个设置（如路由网络或分析社交连接框架）的路径查找障碍时激发新的潜力，并且在增强开发阶段中作为有价值的起点。

以上是在有向图中找到两个顶点之间是否存在路径的详细内容。更多信息请关注PHP中文网其他相关文章！