algorithm - CLRS 深度优先搜索定理 22.10

Question

Theorem 22.10 in CLRS - Introduction to Algorithms说

在无向图 G 的深度优先搜索中，G 的每条边要么是树边，要么是后边。

现在在这里对树边缘部分的解释很明显，但我没有得到后边缘部分。例如：- 取一个无向图，使得

1----2----3

现在，如果首先探索边 1-2 使得 d 1 < d[2]，那么边 1-2 将是树边。现在因为这是一个无向图，所以我们可以说边 2-1 是图中的后边 (d[2] > d 1 ) 吗？

我没有掌握这个后缘的窍门。

Answer 1

我手头没有 CLRS 的副本，所以我是在脑后写下这篇文章。如果我说一些愚蠢的话，请道歉。

如果你有圆圈，你只会得到后边。

对于任何给定的无向图，您可以对边集进行分区，使得每条边都是树边或后边。如果您的原始图恰好已经是一棵树，则后边集将为空。如果您从图中删除所有后边，您的图将变成一棵树。对于给定的图，自然可能存在不止一个这样的分区。

在您的示例中，图 1--2--3 已经是一棵树，因此没有后边。DFS 将只访问每个节点一次。请注意，DFS 永远不会使用相同的边缘两次！因此，如果您已经使用 1-2 从 1 转到 2，则无法通过同一条边从 2-1 返回。

对于无向图来说，循环的概念可能有点难以理解：如果您可以找到两个节点，并且您可以使用多条路径从一个节点到达另一个节点，那么无向图就有一个循环，而您不允许走同一条边两次。

Answer 2

从 wiki链接复制。后边缘是未访问的边缘，它将您从当前节点带到已访问的节点。

Answer 3

最简单的后边缘示例：

  a
 / \
b   c
 \ /
  d

如果您从 a->b->d->c dfs，则边 c->a 是后边，因为它是一条未访问的边，通往已访问的节点。