最小生成树 — mst • igraph 网络分析库

连通图的生成树是具有最小边数的连通子图，它包含图的所有顶点。一个图将有许多生成树。在这些树中，最小生成树将具有最小的边权重之和。

用法

mst(graph, weights = NULL, algorithm = NULL, ...)

graph: 要分析的图对象。
weights: 数值向量，给出图中边的权重。顺序由边 ID 确定。如果选择 unweighted 算法，则忽略此参数。边权重被解释为距离。
algorithm: 用于计算的算法。unweighted 可用于未加权图，prim 运行 Prim 算法用于加权图。如果此值为 NULL，则 igraph 将自动选择算法：如果图具有名为 weight 的边属性，或者 weights 参数不为 NULL，则选择 Prim 算法，否则使用未加权算法。
...: 附加参数，未使用。

具有最小生成森林的图对象。要检查它是否是一棵树，请检查其边数是否为 vcount(graph)-1。原始图的边和顶点属性将保留在结果中。

非连通图的最小生成森林是其所有连通分量的最小生成树的集合。

如果图未连通，则返回最小生成森林。

Prim, R.C. 1957. 最短连接网络和一些推广 贝尔系统技术期刊, 37 1389–1401.


g <- sample_gnp(100, 3 / 100)
g_mst <- mst(g)