algorithm - 如何找到无向图的生成树（不需要 MST）？

Question

我知道解决这个问题的蛮力方法可以给出：

1. 遍历所有边
2. 取一个集合（或列表）（假设 s）
3. 如果将边添加到 s 不会形成循环，则将边添加到 s
4. 如果迭代在所有边上完成，则结束。

但我想要一个有效的解决方案（时间+空间）来解决这个问题。

所以，任何帮助将不胜感激............

Answer 1

假设图是连通的（否则不存在生成树）：从某个任意顶点开始，在图中执行深度优先搜索，记录每个顶点是否已经被访问过，并将每条边输出到您未访问过的顶点遇到。这些边包含一棵生成树，因为它们是无循环的并且会访问每个顶点。

这需要 O(|V|+|E|) 时间和 O(|V|) 空间。