用于检测有向图中的循环的最佳算法
-
06-07-2019 - |
题
检测有向图中所有周期的最有效算法是什么?
我有一个有向图,表示需要执行的作业计划,作业是节点,依赖是边缘。我需要检测此图中循环的错误情况,从而导致循环依赖。
解决方案
Tarjan的强连接组件算法具有 O(| E | + | V |)
时间复杂度。
有关其他算法,请参阅维基百科上的强连接组件。
其他提示
鉴于这是一份工作计划,我怀疑在某些时候你会将它们排序成为一个建议的执行顺序。
如果是这种情况,则 拓扑排序 实施可能在任何情况下检测周期。 UNIX tsort
当然可以。因此,我认为在tsorting的同时检测周期更有效,而不是单独一步。
因此,问题可能变成“我如何最有效地进行切割”,而不是“如何最有效地检测循环”。答案可能是“使用图书馆”,但未通过以下维基百科文章:
具有一个算法的伪代码,以及来自Tarjan的另一个算法的简要描述。两者都有 O(| V | + | E |)
时间复杂度。
从DFS开始:当且仅当在DFS 期间发现后沿时,才存在循环。这被证明是白路理论的结果。
最简单的方法是执行图形的深度优先遍历(DFT)。
如果图形具有 n
顶点,则这是 O(n)
时间复杂度算法。由于您可能必须从每个顶点开始执行DFT,因此总复杂度变为 O(n ^ 2)
。
您必须维护一个堆栈,其中包含当前深度优先遍历中的所有顶点,其第一个元素是根节点。如果你遇到一个在DFT期间已经在堆栈中的元素,那么你有一个循环。
在我看来,在有向图中检测周期最容易理解的算法是图着色算法。
基本上,图形着色算法以DFS方式遍历图形(深度优先搜索,这意味着它在探索另一条路径之前完全探索了一条路径)。当它找到后边缘时,它会将图形标记为包含循环。
有关图形着色算法的深入解释,请阅读本文: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
另外,我在JavaScript中提供了图形着色的实现 https:/ /github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js
如果您无法添加“已访问”属性到节点,使用集合(或映射),只是将所有访问过的节点添加到集合,除非它们已经在集合中。使用唯一键或对象的地址作为“键”。
这也为您提供有关“根”的信息。循环依赖的节点,当用户必须解决问题时会派上用场。
另一个解决方案是尝试查找要执行的下一个依赖项。为此,您必须有一些堆栈,您可以记住您现在的位置以及下一步需要做的事情。在执行之前检查该堆栈上是否已存在依赖项。如果是,你就找到了一个循环。
虽然这似乎具有O(N * M)的复杂性,但您必须记住堆栈的深度非常有限(因此N很小)并且M变得更小,每个依赖关系都可以检查为“ ;执行"另外,你可以在找到一片叶子时停止搜索(所以从不必须检查每个节点 - > M也会很小)。
在MetaMake中,我将图形创建为列表列表,然后在执行时删除每个节点,这自然会减少搜索量。我从来没有必要进行独立检查,这一切都是在正常执行期间自动发生的。
如果您需要“仅测试”,模式,只需添加“干运行”模式。标志,用于禁用实际作业的执行。
没有算法可以在多项式时间内找到有向图中的所有周期。假设有向图有n个节点,每对节点都有相互连接,这意味着你有一个完整的图。因此,这n个节点的任何非空子集指示一个周期,并且存在2 ^ n-1个这样的子集。因此不存在多项式时间算法。 因此,假设您有一个有效的(非愚蠢的)算法,它可以告诉您图中的定向循环数,您可以先找到强连接组件,然后在这些连接的组件上应用算法。由于循环仅存在于组件中而不存在于它们之间。
如果DFS找到指向已访问过的顶点的边,那么你就有一个循环。
根据 Cormen et al。,算法导论 (CLRS):
当且仅当G的深度优先搜索不产生后沿时,有向图G才是非循环的。
在几个答案中已经提到过这个问题;在这里,我还将提供基于CLRS第22章的代码示例。示例图如下所示。
CLRS'深度优先搜索的伪代码读取:
在CLRS图22.4的示例中,图形由两个DFS树组成:一个由节点 u , v , x 组成,和 y ,另一个节点 w 和 z 。每棵树包含一个后边缘:一个从 x 到 v ,另一个从 z 到 z (一个自我循环)。
关键实现是在 DFS-VISIT
函数中,在迭代 u
的 v
时遇到后沿>,遇到 GRAY
颜色的节点。
以下Python代码是CLRS'伪代码的改编,添加了 if
子句,用于检测周期:
import collections
class Graph(object):
def __init__(self, edges):
self.edges = edges
self.adj = Graph._build_adjacency_list(edges)
@staticmethod
def _build_adjacency_list(edges):
adj = collections.defaultdict(list)
for edge in edges:
adj[edge[0]].append(edge[1])
return adj
def dfs(G):
discovered = set()
finished = set()
for u in G.adj:
if u not in discovered and u not in finished:
discovered, finished = dfs_visit(G, u, discovered, finished)
def dfs_visit(G, u, discovered, finished):
discovered.add(u)
for v in G.adj[u]:
# Detect cycles
if v in discovered:
print(f"Cycle detected: found a back edge from {u} to {v}.")
# Recurse into DFS tree
if v not in discovered and v not in finished:
dfs_visit(G, v, discovered, finished)
discovered.remove(u)
finished.add(u)
return discovered, finished
if __name__ == "__main__":
G = Graph([
('u', 'v'),
('u', 'x'),
('v', 'y'),
('w', 'y'),
('w', 'z'),
('x', 'v'),
('y', 'x'),
('z', 'z')])
dfs(G)
请注意,在此示例中,未捕获CLRS'伪代码中的 time
,因为我们只对检测周期感兴趣。还有一些样板代码用于从边列表构建图形的邻接列表表示。
执行此脚本时,它会输出以下输出:
Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.
这些正是CLRS图22.4中示例的后沿。
我这样做的方法是进行拓扑排序,计算所访问的顶点数。如果该数字小于DAG中的顶点总数,则表示您有一个循环。
我在sml中实现了这个问题(命令式编程)。这是大纲。找到具有0的indegree或outdegree的所有节点。这样的节点不能是循环的一部分(因此删除它们)。接下来,从这些节点中删除所有传入或传出边缘。 递归地将此过程应用于结果图。如果最后你没有留下任何节点或边缘,那么图表没有任何周期,否则就有。
https://mathoverflow.net/questions/16393/finding-a-cycle -of-fixed-length 我喜欢这个解决方案,特别适合4长度:)
另外,物理向导说你必须做O(V ^ 2)。我相信我们只需要O(V)/ O(V + E)。 如果图形已连接,则DFS将访问所有节点。如果图形已经连接了子图形,那么每次我们在该子图形的顶点上运行DFS时,我们将找到连接的顶点,并且不必在下一次运行DFS时考虑这些。因此,为每个顶点运行的可能性是不正确的。
正如你所说,你有一组工作,需要按一定的顺序执行。 拓扑排序
给出了调度作业所需的顺序(如果是直接非循环图
,则为依赖问题)。运行 dfs
并维护一个列表,并开始在列表的开头添加节点,如果遇到已访问过的节点。然后你在给定的图中找到了一个循环。
如果图表满足此属性
|e| > |v| - 1
然后图表至少包含循环。