使用Kruskal算法的最小生成树 [英] Minimum spaning tree with Kruskal' algorithm

问题描述

我如何使用Kruskal算法计算im R(3.0.0-Linux x32)最小生成树?

How i can calculate im R(3.0.0 - Linux x32) minimum spanning tree with Kruskal's algorithm?

我使用以下igraph(0.6.5)库创建一个加权全图:

I create an weighted full graph with igraph (0.6.5) library as folws:

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

我能够用Prim(igraph)剪出最小的生树

And i am able to calcutae the minimum spaning tree with Prim (igraph)

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

但是不幸的是，它并未在"igraph"中实施Kruskal的算法.

But unfortunaly doesn't in "igraph" Kruskal's algorithm implemented.

我可以将我的遗传图表示为data.frame:

I can represent my genereted graph as a data.frame:

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

是否有一种简单的方法来计算R中Kruskal的算法的mst?

Is there a simple way to calculate mst with Kruskal's alogithm in R?

推荐答案

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

现在可以绘制和比较两种算法，并定义如下布局算法:

Now is it possible to plot and compare both aloriph with defining a layout algorithm like this:

plot(mstPrim, layout = layout.kamada.kawai, edge.label = E(mstPrim)$weight)
plot(mstKruskal, layout = layout.kamada.kawai, edge.label = mstKruskal$weight)

这篇关于使用Kruskal算法的最小生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！