algorithm - 使用 DFS 创建生成树

Question

在给定的连接和无向图上运行深度优先搜索 (DFS) 算法G = (V,E)可提供生成树。在图上运行 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 会为你做大致相同的事情

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

Answer 2

您的问题是“我可以使用 DFS 在图中找到所有生成树吗？”

那么答案是否定的，我的朋友。DFS 算法在任何时间点的状态都像一列火车，一辆接一辆地连接着。你遍历链条。要找到一棵生成树，您必须前往一个深度 D，其中

D = N，图中的顶点数。

要达到满足上述条件的状态，您必须遍历
v1->v2->v3->v4.....vn-1 -> vn
其中数字表示遍历历史，
vi != vj 其中i,j ∈ {1...n}。& 我 != j

因此，如果存在生成树使得 v1->v3->v4 ... 和 v1->v2 以及 DFS 方法无法产生该结果。

简而言之，您将无法找到任何生成树，其中即使 1 个顶点也包含超过 1 个边。