最小生成树可以在无向图中找到最便宜的路径。但是最小生成森林是什么？它只适用于连通图还是非连通图？
1个回答
18
最小生成森林是无连通图的最小生成树的一般化。对于图的每个组件，取其MST，结果集合即为最小生成森林。
- voidengine
6
1不好意思，我不确定你在说什么。如果你有一个最小生成森林，也就是一个子集，使得每个顶点至少在森林中有一条相邻边，那么它几乎永远不会符合你的定义，这会导致一个更大的森林。 - Labo
@Labo你是在说森林是顶点的子集吗？这根本就没有意义。 - voidengine
1一个最小的顶点子集是一棵森林，因为它是一个没有环的图。我并不是说你的定义是错误的，只是它可以用另一种方式来定义。 - Labo
1那将是一片森林，但绝不是一片跨越的森林。在（不连通的）图中存在路径，则跨越森林中也必定存在路径。定义的措辞可能有所不同，但本质不会改变。 - voidengine
从定义上来看，我认为最小生成森林不包含图中孤立的顶点，这些顶点没有与任何其他顶点相连？ - Alan Evangelista
有两个竞争的定义。跨度森林可以是(1)保留所有顶点的子图森林(如Labo所说)，或者(2)由每个连通分量的生成树组成的子图森林(如voidengine所说)。在数学中，定义(1)更为常见。这可能会让人感到困惑，但请记住，“跨度”实际上只是“保留所有顶点的子图”，并不保证哪些节点仍然连接。生成树保持连通性的唯一原因是否则它将不再是一棵树。此外，最小只意味着权重之和最小。 - FWDekker
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接