什么是树边、前向边、后向边、横叉边？

返回首页

在有向图里求回路，利用深搜方法时候经常会碰到边的判断

一次深度搜索的时间复杂度为O(E)，其中E为边的数目。

深搜过程中把图里面的边分为4种：

1、树边 Tree edge

2、向前边 Forward edge

3、向后边 Back edge

4、横叉边 Cross edge

在求强连通子集时候，也就是求向后边中包含的回路中所有的节点。这些节点可以用一个点来表示，构成新的有向无环图。

在求骨架矩阵的时候，就是把所有的向前边删除，删除向前边不影响整个系统中任何一个节点的可达性。