algorithm - 使用 DFS 创建生成树

Question

在给定的图 G = (V,E) 上运行深度优先搜索 (DFS) 算法，该图是连通且无向的，可提供生成树。在图上运行 DFS 时，当我们到达一个度数大于 1 的顶点时，即 - 有不止一条边连接到它，我们随机选择一条边继续。我想知道选择边(或顶点)以继续的选项是否真的允许使用 DFS 创建给定图的每个生成树？

Answer 1

既然您在评论中提到给定生成树，您需要一些输出同一棵树的 DFS，这应该不是问题。

假设您有所需的生成树和邻接列表形式的图，并且有一个方法 edge_exists(u,v) 返回 true 或 false，具体取决于边是否存在于给定的生成树中。

explore(node):
   visited[node] = 1;
   for v in node.neighbors:
       if edge_exists(node, v) && !visited[v]:
           v.p = node
           explore(v)

顺便说一句，我不认为你需要做一个访问计数，因为你有一个生成树，所以 edge_exisits 会为你做大致相同的事情

通过编程输出生成树，我的意思是给定一个图形输出所有生成树。我不知道该怎么做。