它可以交叉边缘吗？
在一个无向图的情况下，是否有可能向已经访问过的节点租借一个边缘，导致不是当前节点的上升点？
更清楚的是，我想在无向图上实现深度优先搜索。 如果我遇到了一个将我当前的顶点与已经访问过的顶点连接起来的边，我是否可以通过遍历父数组来保证从一个到另一个的路径？
最自然的答案似乎是肯定的。 我还没有找到反例。 你怎么看？
在DFS术语中：
边缘是否可以是DFS中的交叉边缘 - 在无向图中，边缘是否会导致已经发现的节点（它不是起源的祖先）？
由DFS发现的边缘不能是交叉边缘，如果其目的地是已发现的节点，则它必须是后端边缘 - 因此它将导致源节点的祖先（位于DFS树中）。
证明：
假设情况并非如此，并且在某个节点v遇到一个已经发现的节点（ u ），它不是您的“父母”（位于DFS树中）。
既然你发现了这个节点，就有一个边(v,u) 。
但图表是无向的，所以边缘是对称的。
既然u已经发现，你有这些选择：
u被发现并没有“封闭”，在这种情况下，你基本上遍历了一个以u为根的子树，而u确实是v的父亲。 u已经被发现并关闭了。 但考虑到你刚刚发现v ，这是不可能的，并且存在边缘(u,v) 。 因此，导致在无向图中已经发现的边的边必须是后边，并且不能是交叉边。
链接地址: http://www.djcxy.com/p/52381.html