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

---

在计算机科学和图论中，许多现实世界模型场景的解决方案都严重依赖于有向图。这些特殊的图由通过指向其他顶点的有向边连接的顶点组成。确定两个指定点之间是否存在路径是有向图使用中的一个典型问题。在这篇文章中，我们将探讨使用 C++ 解决此问题的各种方法，包括每个过程所需的语法，以确保易于理解。此外，我们将提供详细的算法，仔细说明每种方法，并包含两个可执行的代码示例。

语法

在深入研究细节之前，理解这里使用的基本语言结构至关重要。因此，让我们首先检查语法，然后再继续介绍代码示例。

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

算法

可以使用多种技术来识别有向图中两个顶点之间的路径。本文将重点讨论两种广泛使用的方法：

方法 1：深度优先搜索 (DFS)

• 创建一个访问数组来跟踪遍历期间访问的顶点。

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

• 将 startVertex 标记为已访问。

• 如果 startVertex 与 endVertex 相同，则返回 true，因为存在路径。

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

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

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

方法 2：广度优先搜索 (BFS)

• 创建一个访问数组来跟踪遍历期间访问的顶点。

• 将访问数组的所有元素初始化为 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”，否则继续执行下一步，该步骤涉及探索附近的外部点。在此探索过程中，任何相邻的未探索顶点都会获得“已访问”标记，然后将其放入队列中，以便进行更深入的迭代检查和测试它们是否导致 endVertex 匹配。

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

结论

处理有向图的复杂性在计算机科学开发中可能是一个基本问题。在我们探索使用 C++ 实现的两种流行方法时，缓解这些挑战是我们目标之一。深度优先搜索 (DFS) 和广度优先搜索 (BFS) 处于此类技术的最前沿，它们提供逐步介绍每个算法步骤的过程方法，同时为这两种模型提供可运行的代码示例。一旦掌握了这些方法，在解决多种环境（例如路由网络或分析社会联系框架）中的寻路障碍时，它们就会激发新的潜力，同时在增强开发阶段充当有价值的跳板。