使用Kruskal算法的最小生成树

本文介绍了使用Kruskal算法的最小生成树的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我如何使用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)