C++ 实现有向图可达性判定：广度优先遍历

{"title":"C++ 实现有向图可达性判定：广度优先遍历","description":"本篇文章讲解如何使用 C++ 语言实现有向图的可达性判定，并提供完整代码示例。该算法采用广度优先遍历 (BFS) 方法，并详细分析了时间复杂度。","keywords":"C++, 广度优先遍历, BFS, 有向图, 可达性判定, 图论算法","content":""题目描述："\n"给出一有向图，包含 n 个点，编号从 1~n，m 条边，询问是否能从 a 点走到 b 点。"\n"注：本题为图的广度优先遍历的练习题，所以请用广度优先遍历完成。"\n"\n"输入格式："\n"第一行 4 个整数 n, m, a, b。"\n"接下来 m 行，每行 2 个整数 u，v，表示 u 到 v 有一条有向边。"\n"\n"输出格式："\n"如果能走到输出 Yes，否则输出 No。"\n"\n"输入输出样例："\n"输入："\n"3 2 1 3"\n"1 2"\n"2 3"\n"输出 ："\n"Yes"\n"输入："\n"3 2 1 3"\n"1 2"\n"2 1"\n"输出："\n"No"\n"\n"说明/提示："\n"0<n,m<=200000,a,b,u,v 保证合法"\n"注：时间限制：1.00s 内存限制：128.00MB"\n"\n"可以使用广度优先遍历来解决这个问题。"\n"\n"首先，我们需要使用一个邻接表来表示有向图。邻接表是一个大小为n的数组，每个数组元素是一个链表，链表中存储了与该节点有直接连接的节点。"\n"\n"然后，我们使用一个队列来进行广度优先遍历。初始时，将起始点a加入队列中，并将其标记为已访问。"\n"\n"接下来，我们开始循环遍历队列，直到队列为空。在每一次循环中，我们取出队列的队首元素，将其与所有与其相邻的节点进行比较。"\n"\n"如果相邻节点中有目标节点b，则说明可以从a点走到b点，输出"Yes"，并结束程序。"\n"\n"如果相邻节点中有未被访问过的节点，则将其加入队列，并标记为已访问。"\n"\n"如果循环结束后仍未找到目标节点b，则输出"No"。"\n"\n"以下是C++的实现代码："\n"\n"cpp\"\n\"#include <iostream>\"\n\"#include <vector>\"\n\"#include <queue>\"\n\"using namespace std;\"\n\"\n\"bool bfs(vector<vector<int>>& graph, int start, int end) {\"\n\" int n = graph.size();\"\n\" vector<bool> visited(n, false);\"\n\" queue<int> q;\"\n\" q.push(start);\"\n\" visited[start] = true;\"\n\" \"\n\" while (!q.empty()) {\"\n\" int cur = q.front();\"\n\" q.pop();\"\n\" \"\n\" if (cur == end) {\"\n\" return true;\"\n\" }\"\n\" \"\n\" for (int neighbor : graph[cur]) {\"\n\" if (!visited[neighbor]) {\"\n\" q.push(neighbor);\"\n\" visited[neighbor] = true;\"\n\" }\"\n\" }\"\n\" }\"\n\" \"\n\" return false;\"\n\"}\"\n\"\n\"int main() {\"\n\" int n, m, a, b;\"\n\" cin >> n >> m >> a >> b;\"\n\" \"\n\" vector<vector<int>> graph(n + 1);\"\n\" for (int i = 0; i < m; i++) {\"\n\" int u, v;\"\n\" cin >> u >> v;\"\n\" graph[u].push_back(v);\"\n\" }\"\n\" \"\n\" if (bfs(graph, a, b)) {\"\n\" cout << \"Yes\" << endl;\"\n\" } else {\"\n\" cout << \"No\" << endl;\"\n\" }\"\n\" \"\n\" return 0;\"\n\"}\"\n\""\n"\n"时间复杂度分析："\n"该算法使用了广度优先遍历，时间复杂度为O(n + m)，其中n为节点数，m为边数。"\n