查找有向图中两个顶点之间是否有路径
在计算机科学和图论中,各种实际模型场景的解决方案严重依赖于有向图。这些专门的图由指向其他顶点的有向边锚定的链接顶点组成。确定两个指定点之间是否有路径是使用有向图的一个典型难题。在本篇论文中,我们探讨了使用 C++ 解决这一难题的各种方法,包括每个过程所需的语法,以使事情易于理解。此外,我们将提供详细的算法,细致地说明每种方法,并包括两个可执行代码示例。
语法
在深入研究细节之前,理解这里所用方法的基础语言结构至关重要。因此,在继续代码示例之前,让我们首先检查一下此语法。
bool isPathExists(int startVertex, int endVertex, const vector<vector<int>>& graph);
算法
可以使用多种技术来解决有向图中两个顶点之间的路径识别问题。本文将重点讨论两种广泛使用的方法 -
方法 1:深度优先搜索 (DFS)
创建一个访问数组,以跟踪遍历过程中访问过的顶点。
将访问数组的所有元素初始化为 false。
将 startVertex 标记为已访问。
如果 startVertex 与 endVertex 相同,则返回 true,因为路径存在。
对于当前顶点的每个相邻顶点,以相邻顶点作为新的 startVertex 递归调用 isPathExists 函数。
如果任何递归调用返回 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() { // 示例用法 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 和以邻接列表表示的图形。它初始化一个名为 accessed 的布尔向量以跟踪访问过的顶点。执行此函数时,它首先通过比较 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() { // 示例用法 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 和以邻接列表表示的图形。它初始化一个名为 accessed 的布尔向量以跟踪已访问的顶点,并初始化一个名为 verticesQueue 的队列以存储要处理的顶点。
该函数首先将 startVertex 排入队列并将其标记为已访问。我们的算法的运行始于进入迭代循环,只要其处理队列结构中仍有项目,该循环就会持续存在。随着这种结构化重复的进行,每个循环都会执行两项检查:首先验证当前迭代的出队顶点是否与执行前指定的端点目标匹配;如果两者都成功匹配,则返回"true",否则继续下一步,即探索附近的外围点。在此探索过程中,任何相邻的未探索顶点都会获得"已访问"标签,然后被放入队列中进行更深入的迭代检查,并测试它们是否导致 endVertex 匹配。
如果在所有探索和验证都成功后没有添加到队列,则该函数返回 false。
结论
驾驭有向图的复杂性可能会引起计算机科学发展的一个基本问题。在我们探索用 C++ 实现的两种流行方法时,缓解这些挑战是我们的目标之一。深度优先搜索 (DFS) 和广度优先搜索 (BFS) 站在此类技术的最前沿,提供逐步完成每个算法的程序配方,同时为这两种模型提供工作代码示例。一旦掌握,这些方法将在解决跨多种设置(例如路由网络或分析社交连接框架)的路径查找障碍时激发新的潜力,同时还可作为增强开发阶段的宝贵起点。