生成树与生成森林的区别

Question

概念上，图中的生成树 (Spanning Tree)和生成森林 (Spanning Forest)有何不同？

此外，是否可以通过深度优先搜索 (DFS)或广度优先搜索 (BFS)遍历来构建生成森林？为什么？怎样实现？

我了解生成树，但是我找不到任何关于生成森林的清晰解释。即使是维基百科(https://en.wikipedia.org/wiki/Spanning_tree), 也没有明确定义它。 我的书(Data Structures & Algorithms, Wiley - sixth edition)也没有定义生成森林。

如果我们有一个图，其中有三个连通分量，是否可以通过DFS/BFS遍历构建生成森林呢？

- Nima Salami

---

很简单，你的图的每个连通分量都会生成一棵生成树，所有这些生成树一起被称为生成森林。 - xrisk

@Rishav 谢谢回复。你能举个例子在这张图片上解释一下吗？https://en.wikipedia.org/wiki/Connected_component_(graph_theory)#/media/File:Pseudoforest.svg - Nima Salami

我目前没有照片编辑器，但你是否熟悉连通分量的概念？一个连通分量由所有可以互相到达的顶点组成。在那张图片中有三个这样的连通分量。每个连通分量都用于生成一棵生成树。当你取这三棵生成树的集合时，它被称为生成森林。 - xrisk

@NimaSalami 如有任何疑问，请随时提出。 - Sumeet

Answer 1

当你的图形中只有一个连通组件时，生成树=生成森林。

但是当你的图形中有多个连通组件时。例如在下面的图片中，我们有3个连通组件。

因此，对于每个组件，我们将拥有一个生成树，所有的3个生成树将构成生成森林。

我在想，如果我们有一个图形，例如其中有三个连接的分量，是否有可能通过DFS/BFS遍历构建生成森林？

是的，这是可能的。当只有1个连通组件时，你的BFS或DFS将访问所有顶点并终止，你将拥有一个生成树（在这种情况下等于生成森林）。

但是当你有多于1个连通组件时，就像图片中一样，你唯一需要做的就是从一个未访问的顶点开始另一个BFS或DFS。当没有未访问的顶点时，你的算法终止，每个BFS或DFS遍历将产生一个生成树。

- Sumeet

---

至少根据维基百科当前的版本，这个生成森林的定义并不常见。维基百科文章指出，“生成树森林”的定义有时被称为“完全生成森林”。然而，典型的定义显然是，对于任何无向图 G，只要 H 具有与 G 相同的顶点集，就可以将 H 视为 G 的生成森林，而不需要进一步规定应包括哪些边。 - FWDekker

Answer 2

即使是完全图，也可以通过以下算法构建非平凡生成森林：

前提条件

• 所有顶点都未标记
• 边从1到m进行枚举

边处理

• 如果其相邻顶点都已标记，则跳过该边，因为该边将合并森林中的树或在其中一个树中创建循环
• 否则标记其未标记的相邻顶点

算法
按照它们的枚举顺序处理边

解释：
虽然在构建生成树时添加“跨越”连接组件的边是可行的，但这些边没有在上述算法中添加。

解释：
如果按照升序枚举边的长度，则生成的生成森林的边将是最小生成树的子集，森林中的树将类似于“盆地”，即创建连接组件的边的长度最小，并随着后续步骤中附加的每条边而增加。
在这种情况下，生成森林的属性可以提供原始图的结构特性的见解和/或用于算法。

- user2961818