CLRS - Introduction to Algorithms中的定理22.10说
在无向图G的深度优先搜索中，G的每个边缘是树边缘或后边缘 .
现在在这里对树边缘部分的解释是显而易见的，但我没有得到后边缘部分 . 例如： - 采用无向图表
1 ---- 2 ---- 3
现在，如果首先探索边1-2，使得d 1 <d [2]，那么边1-2将是 tree edge . 现在因为这是一个无向图，所以我们可以说边2-1是图中的后边（d [2]> d 1）??
我没有得到这个后沿的东西 .
CLRS - Introduction to Algorithms中的定理22.10说
在无向图G的深度优先搜索中，G的每个边缘是树边缘或后边缘 .
现在在这里对树边缘部分的解释是显而易见的，但我没有得到后边缘部分 . 例如： - 采用无向图表
1 ---- 2 ---- 3
现在，如果首先探索边1-2，使得d 1 <d [2]，那么边1-2将是 tree edge . 现在因为这是一个无向图，所以我们可以说边2-1是图中的后边（d [2]> d 1）??
我没有得到这个后沿的东西 .
3 回答
我手头没有CLRS的副本，所以我是从脑后写的 . 如果我说一些愚蠢的话，我道歉 .
如果你有圆圈，你只会回到边缘 .
对于任何给定的无向图，您可以对边集进行分区，使每条边都是树边或后边 . 如果原始图形恰好是树，则后边缘集将为空 . 如果从图表中删除所有后边缘，则图形将变为树 . 当然，给定图形可能存在多个这样的分区 .
在您的示例中，图1--2--3已经是树，因此没有后边缘 . DFS将只访问每个节点一次 . 请注意，DFS从不使用相同的边缘两次！因此，如果您已经使用1-2从1到2，则不能从2-1通过相同的边缘返回 .
对于无向图，循环的概念可能有点难以理解：如果你能找到两个节点，你可以使用多个路径从一个节点到另一个节点，无向图有一个循环，你不允许这样做两次走同一条边 .
从wiki复制link . 后沿是 unvisited 边缘，它将您从当前节点带到已访问的节点 .
最简单的后边缘示例：
如果您从a-> b-> d-> c进行dfs，那么边c-> a是后沿，因为它是一个未访问的边到达已经访问过的节点 .