lbi*_*csi 4 algorithm graph depth-first-search
在无向图中，出租给已访问节点的边是否有可能通向不是当前节点的上升节点？
更明确地说，我想在无向图上实现深度优先搜索。如果我遇到将当前顶点与已经访问过的顶点连接起来的边，是否可以通过迭代父数组来保证有一条从一个到另一个的路径？
最自然的答案似乎是肯定的。我还没有找到反例。你怎么认为？
在 DFS 术语中：
边可以是DFS 中
的交叉边吗 - 一条边可以在无向图中通向已发现的节点，该节点不是原点的祖先？
DFS 发现的边不能是交叉边，如果它的目的地是一个已经发现的节点，它必须是一个后边——所以它通向源节点的祖先（在 DFS 树中）。
证明：
假设情况并非如此，并且在某些节点中，v您遇到了一个已经发现的节点 ( u)，它不是您的“父母”之一（在 DFS 树中）。
由于您发现了节点，因此存在边(v,u)。
但是图是无向的，所以边是对称的。
由于u已经被发现，您有以下选择：
u被发现并且尚未“关闭”，在这种情况下，您基本上是在遍历一个u以根为根的子树，并且u确实是v.u已经被发现并关闭了。但考虑到你刚刚发现v，这是不可能的，而且有一个优势(u,v)。因此，在无向图中通向已发现边的边必须是后边，而不能是交叉边。