r - 如何计算R中的最小生成树

Question

给定N个顶点的图以及存储在元组T1 = (d11, d12, …, d1n) to Tn = (dn1, dn2, …, dnn)中的顶点边缘之间的距离。从顶点V1找出该图的最小生成树。同样，打印行进生成的树所需的总距离行进。

Example:
For N =5 
T1 = (0, 4, 5, 7, 5)
T2 = (4, 0, 6, 2, 5)
T3 = (5, 6, 0, 2, 1)
T4 = (7, 2, 2, 0, 5)
T5 = (5, 5, 1, 5, 0)

Selection of edges according to minimum distance are:
V1 -> V2 = 4
V2 -> V4 = 2
V4 -> V3 = 2
V3 -> V5 = 1

Thus, MST is V1 -> V2 -> V4 -> V3 -> V5 and the distance travelled is 9 (4+2+2+1)

从字面上看，我不知道如何在R中创建n个顶点的图。

我在谷歌搜索，但我不明白如何解决上述问题。

请帮我。

Answer 1

您的问题似乎与标题不符-您是在创建图形之后而不是MST吗？正如@ user20650所说，一旦有了图表，MST本身就很简单。

创建大小为n的图形很容易，但是关于哪些节点连接以及它们没有告诉我们的权重(距离)，存在很多复杂性，因此这是一个非常基本的例子。

如果我们假设所有节点都已连接到所有其他节点(全图)，则可以使用make_full_graph。如果不是这种情况，您要么需要数据来说明连接了哪些节点，要么使用随机图。

# create graph
n <- 5
g <- make_full_graph(n)

下一个问题是距离。您尚未提供有关这些距离如何分布的任何信息，但是我们可以演示如何将它们分配给图形。在这里，我将只使用随机统一的[0-1]数字:

# number of edges in an (undirected) full graph is (n2 - n) /2 but
# it is easier to just ask the graph how many edges it has - this
# is more portable if you change from make_full_graph
n_edge <- gsize(g)
g <- set_edge_attr(g, 'weight', value=runif(n_edge))
plot(g)

接下来的就是MST本身，使用 minimum.spanning.tree:

mst <-  minimum.spanning.tree(g)

输出 mst看起来像这样:

IGRAPH dc21276 U-W- 5 4 -- Full graph
+ attr: name (g/c), loops (g/l), weight (e/n)
+ edges from dc21276:
[1] 1--4 1--5 2--3 2--5