我想在 igraph 中手动实现 Bron-Kerbosch 算法。我想用 Wikipedia page 中的图表复制示例.这是我到目前为止提出的解决方案。
library(igraph)
g <- graph.formula(1-2,1-5,5-2,2-3,3-4,4-5,4-6)
P <- as.vector(V(g))
bron_kerbosch <- function(R,P,X) {
if (length(P) == 0 && length(X) == 0) {
print (R)
} else {
for (v in P) {
neis <- as.vector(neighbors(g,v))
bron_kerbosch(union(R,v),intersect(P,neis),intersect(X,neis))
P <- c(P[-which(P==v)])
X <- c(X,v)
}
}
}
> bron_kerbosch(c(),P,c())
[1] 1 2 3
[1] 2 4
[1] 3 5
[1] 4 5
[1] 5 6
答案应该是: [[1, 2, 5], [2, 3], [3, 4], [4, 5], [4, 6]] 我从 1 开始索引,而不是从 0 开始。 知道我做错了什么吗?
最佳答案
我刚刚找到了解决方案。我使用了 g 图的索引,而不是名称:/。 所以我改了两行:
P <- V(g)$name
neis <- neighbors(g,v)$name
这将适用于字符而不是数字。结果:
[1] "1" "2" "5"
[1] "2" "3"
[1] "5" "4"
[1] "3" "4"
[1] "4" "6"
所以顶点没有排序 (5,4) 应该是 (4,5) 但我认为这并不重要。但是,最好将其写入整数而不是字符。
关于r - R中的Bron-Kerbosch算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43173661/