我如何使用 Kruskal 算法计算 im R(3.0.0 - Linux x32) 最小生成树？
我使用 igraph (0.6.5) 库创建一个加权全图，如下所示:
set.seed(1234567890)
g <- graph.full(n = 20)
E(g)$weight <- round(runif(ecount(g)), 2) * 100
我可以用 Prim (igraph) 计算最小生成树
mstPrim <- minimum.spanning.tree(g, algorithm = "prim")
但不幸的是没有在“igraph”中实现 Kruskal 的算法。
我可以将生成的图表示为数据框:
edgeMatrix <- data.frame(cbind(get.edgelist(g), E(g)$weight))
names(edgeMatrix) <- c("from", "to", "weight")
有没有一种简单的方法可以用 R 中的 Kruskal 算法计算 mst？
最佳答案
使用 RBGL 的一个小解决方法包裹:
#convert with graph packagege to BAM class of graph an calculate mst
mstKruskalBAM <- mstree.kruskal(graphBAM(edgeMatrix))
#build new data frame with resut
mstKruskalDF <- data.frame(cbind(t(mstKruskalBAM$edgeList),
t(mstKruskalBAM$weight)))
#convert back to igraph package
mstKruskal <- graph.data.frame(mstKruskalDF, directed=FALSE)
现在可以通过定义这样的布局算法来绘制和比较两个 aloriph 了:
plot(mstPrim, layout = layout.kamada.kawai, edge.label = E(mstPrim)$weight)
plot(mstKruskal, layout = layout.kamada.kawai, edge.label = mstKruskal$weight)
关于r - 使用 Kruskal 算法的最小生成树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16605825/