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

Question

CLRS - Introduction to Algorithms 中的定理 22.10说是

In a depth first search of an undirected graph G, every edge of G is either a tree edge or a back edge.

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

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 返回。

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