R igraph 手册页

mst {igraph}

R 文档

最小生成树

描述

如果一个连通图的子图是一棵树，且其边的权重之和在所有树子图中最小，则该子图为最小生成树。 图的最小生成森林是由其组件的最小生成树组成的图。

用法

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

参数

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

详细信息

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

值

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

作者

Gabor Csardi csardi.gabor@gmail.com

参考

Prim, R.C. 1957. Shortest connection networks and some generalizations Bell System Technical Journal, 37 1389–1401.

参见

components（组件）

示例

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

---