源清除排序总是会返回最大循环吗？

Question

我编写了一个源删除算法来对数据库中的表之间的某些依赖关系进行排序,结果发现我们有一个循环.为简单起见,假设我们有表A,B,C和D.边缘如下:

(A, B)
(B, A)
(B, C)
(C, D)
(D, A)

如您所见,这里有两个循环.一个在A和B之间,另一个在它们之间.这种类型总会在最大的周期中窒息吗？或者不一定是这样吗？

Answer 1

通过源删除我假设你的意思是在每一步删除一个没有传入边的节点.

我认为你要求的是找到你的图的最大欧拉之旅(即一个具有独特边缘的循环,而节点可以重复).

显然,循环中没有顶点可以被删除(循环中的顶点没有零入射边缘),所以这个算法肯定会保留所有周期(和最大的),但是,它仍然没有帮助你找到它,剩下的边缘不能保证是任何循环的一部分(我可以很容易地构造一个示例,其中您描述的算法保留所有边缘,而最大周期仅为2的大小,因此在找到后者时没有太大帮助).

以下是您可以这样做的方法:

• 在图表上执行深度优先搜索.

您感兴趣的是识别后沿,即在遍历中,指向被访问节点的祖先(在DFS树中,由第一次访问节点的边缘引起)的边缘.例如,如果DFS堆栈有节点[A-> B-> C-> D],当您探索D时,您会发现边缘D-> B,这是一个后边缘.每个后边缘定义一个循环.

更重要的是,由后沿引起的周期是图的一组基本周期."一组基本循环":您可以通过基本集的UNIONing和XORing循环构建图的所有循环.例如,考虑循环[A1-> A2-> A3-> A1]和[A2-> B1-> B2-> B3-> A2].您可以将它们连接到循环:[A1-> A2-> B1-> B2-> B3-> A2-> A3-> A1].由于您需要最大周期,因此无需考虑XOR.

• 通过UNIONing在节点处相交的所有基本循环来构造最大循环.(如果你仔细地做,这也应该具有线性时间复杂度).

另一方面,如果你需要一个没有重复顶点的最大循环,那将比线性更难.:)