Kruskal算法求解最小生成树

Question

我该如何使用Kruskal算法在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 算法计算最小生成树？

- frankenstein

Answer 1

使用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)

- frankenstein

Answer 2

我认为ape包中的mst函数实现了这个功能。

http://cran.r-project.org/web/packages/ape/ape.pdf

- Avinash

---

他们没有指定她的算法。而且我无法选择我喜欢执行的算法。 - frankenstein

是的。糟糕！抱歉我没有检查那个。 - Avinash