生成树 VS。跨越森林
Spanning Tree VS. Spanning Forest
生成树和生成林在概念上有什么区别。
另外，是否可以通过DFS或BFS遍历构建生成森林？为什么？怎么样？
我了解生成树，但我找不到任何关于生成林的明确解释。即使是维基百科 (https://en.wikipedia.org/wiki/Spanning_tree)，也没有给出明确的定义。
我的书（Data Structures & Algorithms, Wiley - sixth edition）也没有定义生成森林。
我想知道，如果我们有一个图，其中包含例如三个连接的组件，是否可以通过 DFS/BFS 次遍历构建生成森林？
当你的graph中只有一个连通分量时，spanning tree = spanning forest.
但是当你的图表中有多个 connected components 时。例如在下图中我们有 3 connected components.:
所以对于每个component，我们将有一个spanning tree，所有3 spanning trees将构成spanning forest
I was wondering, if we have a graph with for example three connected
components in it, is it possible to construct a spanning forest by
DFS/BFS traversals?
是的，这是可能的。当只有 1 个 connected component 时，您的 BFS 或 DFS 将终止访问所有顶点，您将有一个 spanning tree (which in this case is equal to spanning forest)。
但是当您有超过 1 个 connected component 时，如图所示，您唯一要做的就是从 [=42= 开始另一个 BFS 或 DFS ]未访问的顶点。当没有 未访问的顶点 并且每个 BFS 或 DFS 遍历将产生 spanning tree.
时，您的算法将终止
Non-trivial 即使对于完整的图，也可以通过以下算法构建生成森林：
先决条件
- 所有顶点都未标记
- 从1到m枚举边
边缘处理
- 如果它的两个相邻顶点都被标记，则跳过它，因为那条边要么合并森林中的树，要么在其中一棵树中创建一个循环
- 否则标记其未标记的相邻顶点
算法
按照枚举的顺序处理边
说明：
虽然在生成树的构造中添加“桥接”连接组件的边是可行的，但上述算法中没有添加这些边。
解读：
如果根据递增长度枚举边，则生成的生成森林的边将是 MST 的子集，并且森林中的树将类似于“盆地”，即创建连接组件的边的长度最小并随着后续步骤中附加的每条边而增加。
在那种情况下，生成森林的属性可以提供对原始图的结构属性的洞察 and/or 并在算法中使用。
生成树和生成林在概念上有什么区别。
另外，是否可以通过DFS或BFS遍历构建生成森林？为什么？怎么样？
我了解生成树，但我找不到任何关于生成林的明确解释。即使是维基百科 (https://en.wikipedia.org/wiki/Spanning_tree)，也没有给出明确的定义。 我的书（Data Structures & Algorithms, Wiley - sixth edition）也没有定义生成森林。
我想知道，如果我们有一个图，其中包含例如三个连接的组件，是否可以通过 DFS/BFS 次遍历构建生成森林？
当你的graph中只有一个连通分量时，spanning tree = spanning forest.
但是当你的图表中有多个 connected components 时。例如在下图中我们有 3 connected components.:
所以对于每个component，我们将有一个spanning tree，所有3 spanning trees将构成spanning forest
I was wondering, if we have a graph with for example three connected components in it, is it possible to construct a spanning forest by DFS/BFS traversals?
是的，这是可能的。当只有 1 个 connected component 时，您的 BFS 或 DFS 将终止访问所有顶点，您将有一个 spanning tree (which in this case is equal to spanning forest)。
但是当您有超过 1 个 connected component 时，如图所示，您唯一要做的就是从 [=42= 开始另一个 BFS 或 DFS ]未访问的顶点。当没有 未访问的顶点 并且每个 BFS 或 DFS 遍历将产生 spanning tree.
Non-trivial 即使对于完整的图，也可以通过以下算法构建生成森林：
先决条件
- 所有顶点都未标记
- 从1到m枚举边
边缘处理
- 如果它的两个相邻顶点都被标记，则跳过它，因为那条边要么合并森林中的树，要么在其中一棵树中创建一个循环
- 否则标记其未标记的相邻顶点
算法
按照枚举的顺序处理边
说明：
虽然在生成树的构造中添加“桥接”连接组件的边是可行的，但上述算法中没有添加这些边。
解读：
如果根据递增长度枚举边，则生成的生成森林的边将是 MST 的子集，并且森林中的树将类似于“盆地”，即创建连接组件的边的长度最小并随着后续步骤中附加的每条边而增加。
在那种情况下，生成森林的属性可以提供对原始图的结构属性的洞察 and/or 并在算法中使用。