原载于 2013-07-12

最后修改于 2013-10-06

注：当时应该是有人在评论中指出了本文的一个错误，于是便有了第二版的修改，不过评论估计是无法找回了。

 

---

 

在一些算法中我们经常需要用到DFS树的性质。我们在这里DFS中原图边的类型进行一些归纳总结，方便诸位对DFS树加深理解。

 

原图中的边一共分为四种类型：

(1)树边(tree edge)

搜索树中存在的边。

(2)前向边(forward edge)

将节点u与其在搜索树中的后代(descendant)v相连的非树边。

(3)后向边(back edge)

将节点u与其在搜索树中的祖先(ancestor)v相连的非树边。

(4)交叉边(cross edge)

其他不属于以上三类的边。

 

大家可以看到，上面四种边的定义涉及到了边与搜索树的关系。所以这里所说的原图中的边都是相对搜索树而言的，也就是说只有在搜索树确定了之后，讨论这四种边才是有意义的。

我们对无向图与有向图分别进行讨论。

1.无向图

考虑下图:

其对应的一种搜索树（森林）为：

 

蓝紫色带箭头的边为树边，表示的是DFS中递归调用的轨迹。由于无向图中前向边和后向边可以认为是等价的，所以红色、黄色虚线边既是前向边也是后向边。

无论以什么样的顺序进行DFS，无向图中都不会存在交叉边。例如假设4、6之间存在一条边（原图中蓝色虚线表示）。若4先于6被访问，那末，在访问4的时候，发现6没有被访问，则会于此对6进行访问，此时形成了父子关系；若6先被访问，则亦然。

边类型的判定

无向图中边类型的判定较为简单。树边就是递归调用经过的边。判断前向/后向边，则只需利用DFS记录顶点是否访问的标记。在访问某个顶点时，若发现一条边与另一个非父节点的已访问节点的相连，则这条边是后向边。

 

 

2.有向图

有向图中的情况则复杂一些。

考虑下图：

 

其对应的一种搜索树（森林）为：

 

蓝紫色边仍然是树边。此时，由于原图中(3, 1)变为了有向边，红色虚线边仅为后向边；同理，由于边(1, 4)有向，黄色虚线边仅为前向边。灰色虚线边则是交叉边。

 

边类型的判定

有向图中，由于边的类型较为复杂，无法直接根据顶点是否访问来进行判定。故需要维护每一个顶点的前序时间戳(Preordering)与后序时间戳(Postordering)。某个顶点的前序时间戳Pre[v]在到达这个顶点尚未进行任何操作时记录，后序时间戳Post[v]则在这个顶点访问完，弹栈之前记录。

据分析可得出以下判定规律：

(1) 递归调用轨迹边为树边。

(2) 对于非树边(u, v)，若有Pre[u]<Pre[v]且Post[u]>Post[v]，则(u, v)为前向边。

(3) 对于非树边(u, v)，若有Pre[u]>Pre[v]且Post[u]<Post[v]，则(u, v)为后向边。

(4) 对于非树边(u, v)，若有Pre[u]>Pre[v]且Post[u]>Post[v]，则(u, v)为交叉边。

(5) 不存在这样的边(u, v)，使得Pre[u]<Pre[v]且Post[u]<Post[v]。