algorithm - 无向图的 DFS 树

Question

所以我得到了什么是无向图的 DFS 树。 这是问题所在:

现在我已经知道答案是(4,3)

但还有哪些未列出的边是不可能的？

(3,6) 会是有效边吗？ (2,4) 或 (3,5) 呢

假设 DFS 树不同分支上的节点不能有边连接它们是否正确？

Answer 1

如原始问题中所述，图 G(V, E) 是无向的。考虑任何一对节点u, v\in V，这样有一条边(u, v)\in E。现在让我们在 DFS(深度优先搜索)中遍历图:

• 如果我们首先到达u，我们最终将访问所有从u 可达的节点，包括v，因此 v 将是 DFS 树中 u(或其子节点)的子节点；
• 如果我们首先到达 v，情况类似，因为图是无向的。

因此，对于任何边 (u, v)\in E，DFS 树中都会有一条路径将 u 连接到 v。现在让我们看看您的案例:

1) (3,6) 会是有效边吗？ (2,4) 或 (3,5) 呢？

• (3, 6):不是有效边。如果有这样的边，3就是6的子节点；
• (2, 4):不是有效边。如果有这样的边，2就是4的子节点；
• (3, 5):不是有效边。如果有这样的边，3就是5的子节点。

2) 假设 DFS 树不同分支上的节点不能有边连接它们是否正确？

如果在无向图中有一条边连接两个节点u和v，那么就会有一条路径e1 e2 ... en 在关联的 DFS 树中将 u 连接到 v(或将 v 连接到 u)。因此，如果 DFS 树中的两个节点位于不同的分支上，则它们之间没有边。