源删除排序总是返回最大循环？ [英] Will a source-removal sort always return a maximal cycle?

问题描述

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

 （A， B）
（B，A）
（B，C）
（C，D）
（D，A）
  / pre> 
 
 
如你所见，这里有两个周期。一个在A和B之间，另一个在四个之间。这种类型的排序总是会在最大的周期上？？吗？或者不一定是这种情况？
解决方案
通过源代码删除我推测你的意思是在每个步骤删除没有传入的节点边缘。
 
 
 
我想你所要求的是找到你的图形的最大欧拉之旅（即具有独特边缘的周期，而节点可以重复） p> 
 
 
显然，循环中没有顶点可以被删除（循环中没有顶点将具有零进入边），所以该算法肯定保留所有循环（和最大），但是仍然，它不能帮助你找到它，剩下的边是不保证是任何循环的一部分（我可以很容易地构建一个例子，你描述的算法保留所有边，而最大的周期只是大小二，因此找不到后者不太有用）。
 
 
 
这样做：
 
 
 
 
 
执行深度优先搜索。 
 
 
 
 
 
您有兴趣识别后边缘，即在遍历中，指向被访节点的祖先（在DFS树中，由第一次的访问节点的边缘引起）。例如，如果DFS堆栈有节点[A-> B-> C-> D]，并且当您探索D时，您将找到一个边缘D-> B，这是一个后沿。 
 
 
 
更重要的是，后边缘引发的周期是一组基本的循环 em>图。 一个基本的循环：您可以通过基本集合的UNIONing和XORing循环来构建图的所有循环。例如，考虑周期[A1-> A2-> A3-> A1]和[A2-> B1-> B2-> B3-> A2]。你可以将它们结合到循环中：[A1-> A2-> B1-> B2-> B3-> A2-> A3-> A1]。因为你想要最大的周期，你不需要考虑XOR。
 
 
 
 
 
通过UNIONing所有相交的基本周期构造最大周期一个节点（如果你仔细地做，这也应该是线性时间复杂度）。
 
 
 
 
 
另一方面，如果你需要没有重复顶点的最大循环，这将比线性更难：）
 
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?
解决方案
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:


Perform a Depth-First Search on your graph. 


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.


Construct the maximal cycle by UNIONing all basic cycles that intersect at a node. (If you do it carefully this should also have a linear time complexity).


On the other hand, if you required a maximal cycle with no repeating vertex, that's going to be much harder than linear :)

                        
这篇关于源删除排序总是返回最大循环？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！