You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

如何在igraph中查找‘直接’连通分量?相关图论术语与实现

问题描述

我对图论不太了解,担心问题标题表述不够准确,所以附上代码说明需求:

library(magrittr)
library(igraph)

df <- data.frame(from = c(1, 1, 2, 2, 6),
                 to = c(2, 4, 3, 5, 3))

graph_from_data_frame(df) %>% 
  components() %>% 
  membership() %>% 
  stack()
#>   values ind
#> 1      1   1
#> 2      1   2
#> 3      1   6
#> 4      1   4
#> 5      1   3
#> 6      1   5

上述代码会找出所有连通分量,但我想要的是类似下面的结果:仅考虑“直接”有向路径,让顶点6不属于组1,只和3连通,因此顶点3会重复出现,同时属于组1和组2:

data.frame(values = c(1, 1, 2, 1, 1, 1, 2),
           ind = c(1, 2, 6, 4, 3, 5, 3))
#>   values ind
#> 1      1   1
#> 2      1   2
#> 3      2   6
#> 4      1   4
#> 5      1   3
#> 6      1   5
#> 7      2   3

我想知道:

  • igraph或R的其他包中有没有实现该功能的函数?优先使用igraph。
  • 这个操作在图论中有没有对应的术语?方便我查找更多相关资料。

解决方案(自我补充)

感谢帮助,我发现可以用igraph::subcomponent()满足需求(之前没在igraph::component()的帮助页底部找到这个函数)。因为我每次只需针对单个指定顶点查找分量,且该函数能区分两种场景:

  1. 获取指定顶点的无向连通分量(所有可达的顶点,不区分方向)
  2. 获取有向路径子分量(仅考虑从指定顶点出发的有向可达顶点,对应我之前说的“简单路径”分量)

示例代码如下:

df <- data.frame(react_id = c("r1", "r1", "r2", "r2", "r6"),
                 depends_on = c("r2", "r4", "r3", "r5", "r3"))

gdf <- igraph::graph_from_data_frame(df)

# 获取指定react_id的所有无向连通分量
igraph::subcomponent(gdf, "r3", "all") |>
  names()
#> [1] "r3" "r2" "r6" "r1" "r5" "r4"

# 获取从r1出发的有向路径子分量
igraph::subcomponent(gdf, "r1", "out") |>
  names()
#> [1] "r1" "r2" "r4" "r3" "r5"

内容的提问来源于stack exchange,提问作者gss

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.08.20 10:48:22