在计算机科学和图论中，解决各种现实生活模型场景的方案严重依赖于有向图。这些专门的图由通过指向其他顶点的有向边连接的顶点组成。确定两个指定点之间是否存在路径是使用有向图的一个典型难题。在本文中，我们将探讨使用C++解决这个困境的各种方法，包括每个过程所需的语法，以确保事情易于理解。此外，我们将详细介绍精心说明每种方法的算法，并包含两个可执行的代码示例。
语法
在深入了解具体细节之前，理解支撑这里方法论的语言结构是至关重要的。因此，在继续查看代码示例之前，让我们首先检查这个语法。
bool isPathExists(int startVertex, int endVertex, const vector& graph);
登录后复制
算法
在有向图中找到两个顶点之间的路径可以使用多种技术来解决。本文将重点讨论两种广泛使用的方法−
方法一：深度优先搜索（DFS）
-
创建一个visited数组来在遍历过程中跟踪已访问的顶点。
-
将visited数组的所有元素初始化为false。
-
将startVertex标记为已访问。
-
如果起始顶点与结束顶点相同，则返回true，表示存在一条路径。
-
对于当前顶点的每个相邻顶点，以相邻顶点作为新的起始顶点，递归调用isPathExists函数。
-
如果任何递归调用返回true，则返回true。
-
如果没有递归调用返回true，则返回false。
方法二：广度优先搜索（BFS）
-
创建一个visited数组来在遍历过程中跟踪已访问的顶点。
-
将visited数组的所有元素初始化为false。
-
创建一个队列来存储待处理的顶点。
-
将startVertex加入队列，并标记为已访问。
-
如果队列不为空，执行以下操作：
-
从队列中出队一个顶点。
-
如果出队的顶点与endVertex相同，则返回true，表示存在一条路径。
-
对于每个被出队的顶点的相邻顶点，如果它尚未被访问，则将其入队并标记为已访问。
-
如果队列变为空并且没有找到路径，则返回 false。
示例1：深度优先搜索（DFS）方法
#include
#include
using namespace std;
bool isPathExists(int startVertex, int endVertex, const vector& graph) {
vector 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 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
