2

我编写了一个源删除算法来对我们数据库中表之间的一些依赖关系进行排序，结果证明我们有一个循环。为简单起见，假设我们有表 A、B、C 和 D。边是这样的：

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

如您所见，这里有两个循环。一个在 A 和 B 之间，另一个在他们四个之间。这种类型的排序总是会在最大的循环中窒息吗？还是不一定如此？

4

2 回答 2

5

我认为源移除是指在每一步移除一个没有传入边的节点。

我认为您要求的是找到图形的最大欧拉之旅（即具有唯一边的循环，而节点可以重复）。

显然，一个循环中的任何顶点都不能被删除（循环中的任何顶点都不会有零传入边），所以这个算法当然会保留所有的循环（和最大的），但是它仍然不能帮助你找到它，剩下的边不能保证是任何循环的一部分（我可以很容易地构建一个示例，您描述的算法保留所有边，而最大的循环只是大小为 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。

  • 通过联合所有在节点处相交的基本循环来构造最大循环。（如果你仔细地这样做，这也应该具有线性时间复杂度）。

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

于 2010-04-06T22:19:50.250 回答
0

您的源删除算法（我将假设这意味着一次删除没有依赖关系的节点，例如 Dimitris）将在任何循环中阻塞。事实上，算法会删除所有不依赖于循环的节点，而你剩下的节点要么是循环的一部分，要么依赖于循环的一部分。

这些循环也称为强连接组件，如果您将每个循环替换为单个节点，您将拥有一个 DAG。

于 2010-11-11T18:47:32.753 回答