我知道至少有两种方法。
一种方法是每次向非循环树添加边时，遍历必要的顶点。
缺点是随着树变大，遍历过程需要越来越多的时间。
另一种方法是被动检查添加的边缘是否创建了无限循环。
问问题
112 次
2 回答
2
我不确定拓扑排序在哪里出现，所以这里有一个答案，你只是在节点之间创建链接。
一开始假设您只有一组断开连接的节点。当您添加链接时，您通过链接它们将节点变成树。如果您创建一个链接来添加两个先前独立的树，那么您并没有创建一个循环。如果在已经位于同一棵树中的两个节点之间添加链接，则会创建一个循环。因此，您可以通过检查要链接的两个节点是否已经在同一棵树中来检查循环。
这是联合查找，在http://en.wikipedia.org/wiki/Disjoint-set_data_structure中描述了一种有效的方法。
于 2012-11-17T05:29:21.207 回答
0
我对您提到拓扑排序感到困惑，因为如果您进行拓扑排序，您将免费获得循环检测，这在http://en.wikipedia.org/wiki/Topological_sort等大量地方都有解释。您还将从http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29#Algorithms获得周期检测。
考虑到这一点，我想知道您是否正在尝试在有向图中进行在线循环检测。我想我曾经在 Unix 中检测到用户代码产生的死锁的东西中看到了一些代码——它是迭代的，并且依赖于一个进程只能等待一个事件的事实。我认为这对应于您的“遍历必要的顶点”。
似乎有许多方案依赖于维护拓扑排序顺序。然后，如果您添加与顺序一致的链接，您就知道您没有引入循环。问题是，如果您添加的链接与订单不一致，您必须检查周期并维护订单。http://homepages.ecs.vuw.ac.nz/~djp/files/tr0703.pdf中描述了三种这样的算法
于 2012-11-17T06:54:43.650 回答