graph-theory - 我们如何检查节点 B 是否可以从节点 A 访问，以便我们可以在混合图中再次返回到 A（同时具有直接边和非直接边）？

我们得到一个混合图（具有两种类型的边），我们被要求找到没有顶点，例如我们可以从一个顶点（让 A）遍历到一个顶点（让 B，连接到 A）并且可以再次返回来自任何路径的前一个顶点 (A)。

我应该在这里使用哪种方法？

标签： graph-theory

我假设该图是未加权的，并且通过在每次 BFS 遍历时存储前驱/父注释，我们将获得到 dest 顶点的最短路径。

因此，只需从顶点 A 开始运行 BFS 即可获得直到 B 的路径。

由于您的图形包含有向链接以及从 A-> B 的路径可能与路径 B-> A 不同，因此我们再次以顶点 B 作为源进行 BFS 以返回到 A。