如何在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个顶点组成的图。

我在谷歌上搜索了一下，但是没有理解如何解决上述问题。

请帮助我。

- Navya

---

将您的权重转换为相邻矩阵：adj = rbind(T1, T2, T3, T4, T5)，然后读入 igraph：g = graph_from_adjacency_matrix(adj, weighted = TRUE)。然后您就可以计算 mst 了。 - user20650

那些 T1，T2，T3，T4，T5 是从顶点到距离。我怎么才能在创建图之前知道这些距离呢？ - Navya

你能否解释一下你上面的评论的意思：“在此之前我怎么知道这些距离”，因为你的问题说明了这些距离是已知的。 - user20650

我认为你可以只使用 mst(g)，但也许可以使用 mst(g, weights = E(g)$weights)？ - user20650

sum(E(mg)$weight)，其中 mg 是最小生成树图。 - user20650

Answer 1

您的问题似乎与标题不符-您需要创建图形而不是最小生成树吗？一旦您获得了一个图，就像@user20650所说的那样，最小生成树本身就很容易。

创建大小为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

- David_O

---

我也不知道距离是如何计算的，所以我很困惑。我已经发布了完整的问题。他们只提供了那么多信息。而且我对这个MST主题还很陌生。 - Navya

我们无法提供帮助。如果您在图形结构方面没有超过_n_个节点的信息，则只能在某些假设下给出通用答案。您可以使用随机图和不同的边长度分布，代码仍将给出答案。 - David_O

是的，我知道如果没有图表和距离信息很难提供帮助。有了那些信息，user20650 帮了我一个忙。这已经足够了。 - Navya

顺便说一下，你的回答对我很有用，因为我知道了如何在R中制作一个n图。谢谢。 - Navya