igraph是否存在has_path函数？Python NetworkX代码迁移至R igraph咨询

核心思路 #

通过两步向量化操作实现需求，全程调用igraph内置函数避免手动循环，性能可支持万级顶点规模的图：

• 第一步：计算所有顶点对的可达性矩阵
• 第二步：过滤掉存在直接连边的顶点对，剩下的就是符合要求的结果

实现代码 #

以有向图为例，无向图逻辑完全一致：

library(igraph)

# 示例图构造，可替换为你自己的图对象
g <- sample_gnm(10, 15, directed = TRUE)

# 1. 生成可达性矩阵：矩阵元素[i,j]为TRUE表示顶点i到顶点j存在可达路径
reach_mat <- is_reachable(g, V(g), V(g))
# 去掉对角线（排除自己到自己的无效结果）
diag(reach_mat) <- FALSE

# 2. 生成直接邻接矩阵：矩阵元素[i,j]为TRUE表示i和j有直接连边
adj_mat <- as_adjacency_matrix(g, sparse = FALSE) > 0

# 3. 取交集：可达且无直接连边的顶点对
result_mat <- reach_mat & !adj_mat

# 如需输出顶点对列表而非矩阵，可执行以下代码：
result_pairs <- which(result_mat, arr.ind = TRUE)
# 替换索引为顶点名（如果你的图设置了顶点名）
result_pairs[,1] <- V(g)$name[result_pairs[,1]]
result_pairs[,2] <- V(g)$name[result_pairs[,2]]
colnames(result_pairs) <- c("source", "target")

如果你使用的是无向图，结果会出现对称的重复顶点对，可加一行代码去重：

result_pairs <- result_pairs[result_pairs[,1] < result_pairs[,2], ]

关键函数说明 #

• is_reachable() 对应NetworkX中has_path函数的向量化实现，一次调用即可计算所有源点到所有目标点的可达性，比循环调用单个判断效率高10~100倍
• 如果图规模特别大（顶点数>1e4），可以改用稀疏矩阵运算：将as_adjacency_matrix的sparse参数设为TRUE，可达性矩阵也可以通过distances函数转换得到：reach_mat <- !is.infinite(distances(g))，效果完全一致

内容的提问来源于stack exchange，提问作者Dragno