无向图中的深度优先搜索 - 是否可能存在横叉边？

Question

在无向图中，一个指向已经访问过的节点的边是否可能导向当前节点的非祖先顶点？

更明确地说，我想在无向图上实现深度优先搜索。如果我遇到一个连接当前顶点和已经访问过的顶点的边，那么通过迭代父数组，我能否保证从一个顶点到另一个顶点存在一条路径？

最自然的答案似乎是肯定的。我还没有找到反例。你认为呢？

以DFS术语来说：
在无向图中，一个边是否可以是交叉边 - 即导向一个已经发现的非起点祖先节点的边？

- lbicsi

---

更新：我只考虑将深度较大的节点与深度较小的节点连接起来的边缘。 - lbicsi

我冒昧地在你的问题中添加了正式的DFS术语，如果您觉得不满意，请随时回滚。 - amit

你所说的“parent”是指直接父级还是祖先级？ - advocateofnone

Answer 1

通过 DFS 所发现的边不可能是横叉边，如果其终点是一个已经被发现的节点，则一定是后向边 - 因此它指向源节点的祖先（在 DFS 树中）。

证明：

假设不是这样，并且当在某个节点 v 时遇到一个已经被发现的节点（u），它不是您的“父节点”之一（在 DFS 树中）。 由于您发现了节点，因此存在一条边 (v, u)。 但是图是无向的，因此边是对称的。

由于 u 已被发现，您有以下选项：

1.u已被发现但尚未“关闭”，在这种情况下，您基本上正在遍历以 u 为根的子树，而 u 确实是 v 的父亲。 2.u 已被发现并已关闭。但考虑到您刚刚发现了 v，并且有一条边 (u,v)，这是不可能的。

因此，在无向图中，导致已发现的边的边必须是后向边，不能是横叉边。

- amit

---

那么，如果v不是“刚刚”被发现的情况呢？换句话说，如果我的搜索已经完成了找到某些子树，然后我找到一条边，它链接到一个最初没有被访问但在此期间被访问的节点，那么这个邻居应该是节点已经处理过的子树的一部分，对吗？ - lbicsi

@lbicsi，我不明白你的问题，因为在我看来，它难道不正好符合第二种情况吗？ - amit

你对原问题“在DFS中，一条边可以是横叉边吗？”的回答是“是”吗？ - beaker

@beaker 不，我编辑了问题，使其相反，而没有编辑我的问题，让我来修复它。谢谢你的评论。 - amit

太好了，这样就清楚多了。 :) - beaker