algorithm - 关注深度优先搜索

Question

证明如果 G 是一个无向连通图，那么它的每条边要么在深度优先搜索树中，要么是后边。

现在，从直觉和 Steven Skiena 的课堂讲授中，我知道上面的说法是正确的，因为它一直向下俯冲，然后将绳子扔回之前的顶点。我也知道 DFS 非常适合寻找周期。

但是，我的问题是我不知道如何“证明”边缘是树边缘或后边缘。

Answer 1

考虑可能的 4 种情况（理论上）。边缘可以是：

1. 树的边缘
2. 后缘
3. 树边缘和后边缘
4. 既不是树边缘也不是后边缘

为了证明需要什么，您需要证明情况 3 和 4 不可能发生，即导致矛盾。