CLRS - Introduction to Algorithms中的定理22.10表示
在无向图g的深度优先搜索中，g的每一条边要么是树边，要么是后边。
在这里，对树边缘部分的解释是显而易见的，但是我没有得到后边缘部分。
例如：取一个无向图，这样
1----2----3个
现在在这里，如果首先探索边缘1-2，使得d1d1）？是吗？
我不明白这个后缘的事。
最佳答案
我手头没有CLR的副本，所以我是从脑后开始写的。如果我说了傻话，我会道歉的。
只有当你有圆的时候你才能得到后边缘。
对于任何给定的无向图，可以对边集进行分区，使每条边都是树边或后边。如果原始图形碰巧已经是一棵树，则后边集将为空如果从图中删除所有后边缘，则图将成为树自然地，对于给定的图，可能存在不止一个这样的划分。
在您的示例中，图1--2--3已经是一棵树，因此没有后边dfs将只访问每个节点一次。请注意，DFS从不使用同一条边两次所以如果你已经用了1-2从1到2，你就不能通过同样的边从2-1返回。
对于无向图，循环的概念可能有点难以理解：如果可以找到两个节点，从而可以使用多条路径从一个节点到另一个节点，并且不允许在同一条边上行走两次，则无向图有一个循环。