igraph 有 "has_path" 功能吗？

Question

我正在尝试将代码从 python NetworkX 移植到 R igraph。在 NetworkX 中，有一个名称为 has_path 的函数，用于查找两个顶点是否有路径。我想以一种有效的方式找到图形中没有边但有路径的所有顶点。

Answer 1

我认为你可以使用下面的代码来检查是否存在从顶点 V1 到 V2 的路径（该图可以是有向的也可以是无向的）

c(!is.infinite(distances(g, V1, V2, mode = "out")))

Answer 2

如果您需要在 无向 图中重复检查，只需将其分解为连接的组件并检查两个顶点是否在同一组件内。这将非常有效，因为组件只需要找到一次。

参见components函数。它为您提供了一个成员向量。需要检查两个顶点对应的位置是否有相同的值（相同的组件索引）。

如果图是有向的，最简单的解决方案是@ThomasIsCoding 发布的解决方案。这对于一次性检查来说完全没问题。加快重复检查的速度会带来更多麻烦，并且有其自身的问题。