graph - 首次访问的节点形成一棵在 BFS 和 DFS 中具有相同边数的生成树

Question

我试图说明该陈述是否正确：
在 DFS/BFS 期间，第一次访问的节点形成一棵生成树，无论您使用 DFS 还是 BFS，它都具有相同数量的边。
这是真的吗？谢谢！

标签： graphdepth-first-searchbreadth-first-searchspanning-tree

Answer 1

是的，DFS 和 BFS 生成具有相同边数的树。DFS 和 BFS 创建不同形状的树。但在这两种情况下，每个顶点都通过一条边与其相邻顶点相连。树上没有圆圈。那么 DFS 和 BFS 的边数应该相同。