源删除排序是否总是返回最大循环？
我编写了一个源删除算法来对数据库中表之间的一些依赖关系进行排序，结果发现我们有一个循环。为了简单起见，假设我们有表 A、B、C 和 D。边是这样的：
(A, B)
(B, A)
(B, C)
(C, D)
(D, A)
如您所见，这里有两个循环。一个位于 A 和 B 之间，另一个位于所有四个之间。这种类型的排序会总是在最大的循环中被阻塞吗？或者说情况并不一定如此？
I wrote a source-removal algorithm to sort some dependencies between tables in our database, and it turns out we have a cycle. For simplicity, let's say we have tables A, B, C, and D. The edges are like this:
(A, B)
(B, A)
(B, C)
(C, D)
(D, A)
As you can see, there are two cycles here. One is between A and B and another is between all four of them. Will this type of sort always choke on the largest cycle? Or is that not necessarily the case?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
通过源删除，我认为您的意思是在每一步中删除没有传入边缘的节点。
我认为您要求的是找到图的最大欧拉之旅（即具有唯一边缘的循环，而节点可以重复）。
显然，循环中的任何顶点都不能被删除（循环中没有顶点的传入边为零），因此该算法当然保留了所有循环（以及最大的循环），但它仍然无法帮助您找到< /em> 它，剩余的边不保证是任何循环的一部分（我可以轻松构建一个示例，其中您描述的算法保留所有边，而最大的边循环的大小仅为二，因此对于找到后者没有太大帮助）。
您可以按照以下方式执行此操作：
您有兴趣识别后边，即在遍历中，指向祖先的边（在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]。由于您想要最大周期，因此不需要考虑异或。
另一方面，如果您需要没有重复顶点的最大循环，那就是比线性困难得多:)
By source-removal I presume you mean at each step removing a node with no incoming edges.
What I think you are asking for is finding the maximal Euler tour of your graph (i.e. a cycle with unique edges, while nodes can be repeated).
Obviously, no vertex in a cycle can be removed (no vertex in the cycle would have zero incoming edges), so this algorithm certainly preserves all cycles (and the biggest), but still, it doesn't help you find it, the remaining edges are not guaranteed to be part of any cycle (I can easily construct an example where the algorithm you describe retains all edges, while the largest cycle is merely of size two, thus not too helpful in finding the latter).
Here is how you can do it instead:
You are interested in recognizing back edges, i.e., in the traversal, an edge which points back to an ancestor (in the DFS tree, which is induced by edges of visiting nodes for the first time) of the visited node. For example, if the DFS stack has nodes [A->B->C->D] and while you explore D you find an edge D->B, that's a back edge. Each back edge defines a cycle.
More importantly, the cycles induced by back-edges are a basic set of cycles of the graph. "A basic set of cycles": you can construct all cycles of the graph just by UNIONing and XORing cycles of the basic set. For example, consider the cycles [A1->A2->A3->A1] and [A2->B1->B2->B3->A2]. You can union them to the cycle: [A1->A2->B1->B2->B3->A2->A3->A1]. Since you want the maximal cycle, you don't need to consider XORs.
On the other hand, if you required a maximal cycle with no repeating vertex, that's going to be much harder than linear :)
您的源删除算法（我假设这意味着一次删除一个没有依赖关系的节点，例如 Dimitris）将在任何周期中阻塞。事实上，算法将删除所有不依赖于循环的节点，而剩下的节点将要么是循环的一部分，要么依赖于属于循环的节点。
这些循环也称为强连接组件，如果您用单个节点替换每个循环，您将有一个 DAG。
Your source removal algorithm (which I will assume means removing nodes with no dependencies one at a time, like Dimitris) will choke on any cycle. In fact, algorithm will remove all nodes that don't depend on the cycles, and the nodes you have left over will either be part of a cycle or depend on a node that is part of a cycle.
Those cycles are also called strongly connected components, and if you replaced each cycle with a single node you would have a DAG.