R语言使用igraph包如何判断图中指定节点集是否连通

核心思路 #

• 先做入参合法性校验：检查传入的所有目标节点都存在于输入的图对象中，避免非法输入报错
• 提取目标节点对应的诱导子图：子图仅保留传入的目标节点，以及这些节点之间在原图中直接存在的连边，自动排除不在节点集内的中转节点
• 调用igraph内置的连通性判断函数，检查该诱导子图是否为连通图，是则返回TRUE，否则返回FALSE

函数代码 #

library(igraph)

check_nodes_connectivity <- function(graph_obj, node_set) {
  # 校验节点是否全部存在
  if (!all(node_set %in% V(graph_obj)$name)) {
    stop("输入的节点存在不在图中的无效值，请检查后重试")
  }
  # 生成目标节点的诱导子图
  target_subgraph <- induced_subgraph(graph_obj, vids = node_set)
  # 判断子图连通性并返回结果
  return(is_connected(target_subgraph))
}

测试验证 #

用提供的示例图和测试用例运行，结果完全符合预期：

# 构建示例图
df <- data.frame(a = c("a","a","a","b","c","f"),
                 b = c("b","c","e","d","d","e"))
my.graph <- graph.data.frame(df, directed = FALSE)

# 测试用例1
check_nodes_connectivity(my.graph, c("b", "a", "c"))
#> [1] TRUE

# 测试用例2
check_nodes_connectivity(my.graph, c("b", "a", "e"))
#> [1] TRUE

# 测试用例3
check_nodes_connectivity(my.graph, c("b", "a", "f"))
#> [1] FALSE

补充说明：第三个测试用例返回FALSE的原因是，传入的节点集不含中转节点e，诱导子图中f和a、b没有直接连边，属于孤立节点，因此子图不连通，和预期结果一致。如果后续需要支持“允许通过节点集外的节点中转判断连通性”的场景，只需要修改逻辑为：检查节点集内任意两节点在原图中是否都可达即可。

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