极客笔记C++ 在有向图中查找两个顶点之间是否存在路径
在计算机科学和图论中，解决各种现实生活中的模型场景通常依赖于有向图。这些专门的图由相互连接的顶点组成，这些顶点通过指向其他顶点的有向边进行锚定。确定两个指定点之间是否存在路径是使用有向图的一个典型问题。在本文中，我们将使用C++探讨解决这个问题的各种方法，包括每个过程所需的语法以保持易理解性。此外，我们还将提供详细的算法，详细说明每种方法，并包括两个可执行的代码示例。
语法
在深入了解具体细节之前，首先了解支撑该方法论的语言结构是至关重要的。因此，在进入代码示例之前，先来看一下这个语法结构。
bool isPathExists(int startVertex, int endVertex, const vector<vector<int>>& graph);
步骤
在有向图中找到两个顶点之间的路径可以使用多种技术来解决。本文将重点讨论两种广泛使用的方法：
方法1：深度优先搜索（DFS）
- 创建一个visited数组来跟踪遍历过程中访问过的顶点。
-
将visited数组的所有元素初始化为false。
-
将startVertex标记为已访问。
-
如果startVertex与endVertex相同，则返回true，表示存在一条路径。
-
对于当前顶点的每个相邻顶点，递归调用isPathExists函数，新的startVertex为相邻顶点。
-
如果任何递归调用返回true，则返回true。
-
如果没有递归调用返回true，则返回false。
方法2：广度优先搜索（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，否则继续下一步，即探索附近的外围点。在这个探索过程中，任何相邻的未探索顶点在放入队列进行深层迭代检查并测试是否与endVertex匹配之前会被标记为visited。
如果在所有的探索和验证之后没有任何添加到队列的情况下，函数将返回false。
结论
在计算机科学开发中，处理有向图的复杂性可能是一个基本问题。为了缓解这些挑战，我们探索了用C++实现的两种常见方法。深度优先搜索（DFS）和广度优先搜索（BFS）是这些技术的前沿，它们提供了逐步进行算法的过程性方法，并为这两种模型提供了工作代码示例。一旦掌握了这些方法，就可以在多个环境中解决路径发现障碍，如路由网络或分析社交连接框架，并作为增强开发阶段的有价值的跳板。