生成树VS. 跨越森林
Nim*_*ami 6 algorithm graph-theory breadth-first-search spanning-tree depth-first-search
在概念上,图表中的生成树和生成森林之间有什么区别.
此外,是否可以通过DFS或BFS遍历构建生成林？为什么？怎么样？
我理解生成树,但我找不到任何关于跨越森林的明确解释.甚至维基百科(https://en.wikipedia.org/wiki/Spanning_tree)也没有给出明确的定义.我的书(数据结构和算法,Wiley - 第六版)也没有关于跨越森林的定义.
我想知道,如果我们有一个图表,例如其中包含三个连接组件,是否可以通过DFS/BFS遍历构建生成林？
Sum*_*eet 11
如果您的连接组件中只有一个graph,则spanning tree = spanning forest.
但是当connected components图表中有多个时.例如,在下面的图片中我们有3个 connected components.:
因此,对于每一个component,我们将拥有一个spanning tree,并且所有3个 spanning trees将构成spanning forest
我想知道,如果我们有一个图表,例如其中包含三个连接组件,是否可以通过DFS/BFS遍历构建生成林？
对的,这是可能的.当只有1时connected component,你BFS或DFS将终止访问所有顶点,你将有一个spanning tree (which in this case is equal to spanning forest).
但是当你有超过1时connected component,就像在图片中一样,你唯一需要做的就是从另一个BFS或DFS从未访问的顶点开始.当没有未访问的顶点时,您的算法会终止,每个BFS或DFS遍历将产生一个spanning tree.