使用Kruskal算法的最小跨越樹

Question

我如何用Kruskal算法計算最小生成樹im R（3.0.0 - Linux x32）？

我創建一個加權全圖用的igraph（0.6.5）庫作爲folws：

set.seed(1234567890) 
g <- graph.full(n = 20) 
E(g)$weight <- round(runif(ecount(g)), 2) * 100 

，我能夠用普里姆（IGRAPH）到calcutae最小企業跨越式樹

mstPrim <- minimum.spanning.tree(g, algorithm = "prim") 

但不幸的是並沒有在「igraph」Kruskal的算法中實現。

我可以代表我的genereted圖作爲一個data.frame：

edgeMatrix <- data.frame(cbind(get.edgelist(g), E(g)$weight)) 
names(edgeMatrix) <- c("from", "to", "weight") 

有沒有一種簡單的方法來計算與克魯斯卡的R中alogithm MST？

Answer 1

我覺得在ape包中的mst函數實現了這一點。

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

Answer 2

一個小的解決辦法與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)