给定一个无向图中的节点 x，该节点已知是连通分量的一部分，我试图找到属于 x 的分量的所有节点。
我当前的实现识别无向图中的所有组件，因此对于大型图来说是无效的。我目前使用 ggm 库中的 connectedComp 来执行此操作，但宁愿从节点 x 开始从 RBGL 运行 BFS，并在其组件被完全探索后终止。关于如何执行此操作的任何建议？此外，如能提供有关可从 R 调用的并行图算法实现的任何信息，我们将不胜感激。
library("ggm")
x <- 2
> graph
1 2 3 4 5 6 7 8 9 10
1 0 0 0 0 0 0 0 0 0 0
2 0 0 1 0 0 1 0 0 0 0
3 0 1 0 0 0 1 1 1 0 0
4 0 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0 0
6 0 1 1 0 0 0 0 0 0 0
7 0 0 1 0 0 0 0 0 0 0
8 0 0 1 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0 0
graph_object <- as(graph, "graphNEL")
# All connected components of graph using connectedComp function:
comp_list <- connectedComp(graph_object)
> comp_list
$`1`
[1] "1"
$`2`
[1] "2" "3" "6" "7" "8"
$`3`
[1] "4"
$`4`
[1] "5"
$`5`
[1] "9"
$`6`
[1] "10"
# Extract adjacency matrix of component containing x:
comp_x <- seq_along(comp_list)[sapply(comp_list, FUN=function(list) x %in% list)]
> comp_x
[1] 2
comp_x_list <- comp_list[[comp_x]]
> comp_x_list
[1] "2" "3" "6" "7" "8"
comp_x <- graph[comp_x_list, comp_x_list]
> comp_x
2 3 6 7 8
2 0 1 1 0 0
3 1 0 1 1 1
6 1 1 0 0 0
7 0 1 0 0 0
8 0 1 0 0 0
最佳答案
在我看来用 Union-find 预处理图形会给你最好的结果。
如果将图形存储为边列表而不是邻接矩阵，速度会更快。
如果您需要并行解决方案，那么您应该阅读 bfs in hadoop
关于algorithm - R 中无向图中的快速连通分量识别，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9999057/