유방향 그래프에서 두 정점 사이에 경로가 있는지 확인

在计算机科学和图论中，解决各种现实生活模型场景的方案严重依赖于有向图。这些专门的图由通过指向其他顶点的有向边连接的顶点组成。确定两个指定点之间是否存在路径是使用有向图的一个典型难题。在本文中，我们将探讨使用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 중국어 웹사이트의 기타 관련 기사를 참조하세요!