CLRS深度优先搜索定理22.10

Question

定理22.10在CLRS -算法简介中说

在无向图G的深度搜索中，G的每一条边都是树边或后边。

现在，对于树边缘部分的解释是显而易见的，但是我没有得到后面的边缘部分。例如：-取一个无向图，以便

1-2-3

现在，如果首先探索边缘1-2，使d1 < d2，那么edge 1-2将是树边缘。既然这是一个无向图，那么我们可以说，边2-1是图中的后边(d2 > d1)吗?？

我不懂这个后边的窍门。

Answer 1

我手边没有CLRS的副本，所以我是从后脑勺写的。如果我说了些蠢话，我很抱歉。

只有在有圆圈的情况下才能得到回边。

对于任何给定的无向图，您可以划分边缘集，这样每个边都是树边或后边。如果您的原始图形碰巧已经是一棵树，则后面的边缘集将为空。如果你从图中移除所有后边，你的图就会变成一棵树。当然，对于给定的图，可能存在多个这样的分区。

在你的例子中，图1-2-3已经是一棵树了，所以没有后边。DFS将访问每个节点一次。请注意，DFS从未两次使用相同的边缘！因此，如果您已经使用1-2从1到2，您不能通过同一边缘从2-1返回。

对于无向图，循环的概念可能有点难理解:一个无向图有一个循环，如果您可以找到两个节点，这样就可以使用多条路径从一个节点到另一个节点，在该路径中，不允许您两次走同一条边。

Answer 2

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

Answer 3

最简单的后缘例子：

  a
 / \
b   c
 \ /
  d

如果您的dfs来自a->b->d->c，则边缘c->a是后边缘，因为它是一个未访问的边缘，它指向已经访问过的节点。