关键的实现是,在 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 ' pseudocode is not captured because we'中的 time 仅对检测周期感兴趣 . 还有一些样板代码用于从边列表构建图形的邻接列表表示 .
执行此脚本时,它会输出以下输出:
Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.
14 回答
鉴于这是一份工作计划,我怀疑在某些时候你会将它们分类为一个建议的执行顺序 .
如果是这种情况,那么topological sort实现可以在任何情况下检测周期 . UNIX
tsort
当然可以 . 因此,我认为在tsorting的同时检测周期更有效,而不是在单独的步骤中检测周期 .因此,问题可能变成“我如何最有效地进行切割”,而不是“我如何最有效地检测循环” . 答案可能是“使用库”,但未能遵循以下维基百科文章:
具有一种算法的伪代码,以及来自Tarjan的另一种算法的简要描述 . 两者都有
O(|V| + |E|)
时间复杂度 .Tarjan's strongly connected components algorithm具有
O(|E| + |V|)
时间复杂度 .有关其他算法,请参阅维基百科上的Strongly connected components .
从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变小,每个依赖关系都可以检查为"executed"加上你可以当你找到一片叶子时停止搜索(所以你必须检查每个节点 - > M也会很小) .
在MetaMake中,我将图形创建为列表列表,然后在执行时删除每个节点,这自然会减少搜索量 . 我从来没有必要进行独立检查,这一切都是在正常执行期间自动发生的 .
如果您需要“仅测试”模式,只需添加一个“干运行”标志,该标志禁用实际作业的执行 .
没有算法可以在多项式时间内找到有向图中的所有周期 . 假设有向图有n个节点,每对节点都有相互连接,这意味着你有一个完整的图 . 因此,这n个节点的任何非空子集指示一个周期,并且存在2 ^ n-1个这样的子集 . 因此不存在多项式时间算法 . 因此,假设您有一个有效的(非愚蠢的)算法,可以告诉您图中的定向循环数,您可以先找到强连接组件,然后在这些连接的组件上应用算法 . 由于循环只存在于组件而不是它们之间 .
我在sml(命令式编程)中实现了这个问题 . 这是大纲 . 找到具有0的indegree或outdegree的所有节点 . 这样的节点不能是循环的一部分(因此删除它们) . 接下来,从这些节点中删除所有传入或传出边缘 . 递归地将此过程应用于结果图 . 如果最后你没有任何节点或边缘,图表没有任何周期,否则它有 .
如果DFS找到指向已访问过的顶点的边,那么就有一个循环 .
我这样做的方法是进行拓扑排序,计算所访问的顶点数 . 如果该数字小于DAG中的顶点总数,则表示您有一个循环 .
https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length我喜欢这个解决方案最好特别为4长:)
另外,物理向导说你必须做O(V ^ 2) . 我相信我们只需要O(V)/ O(V E) . 如果图形已连接,则DFS将访问所有节点 . 如果图形已经连接了子图形,那么每次我们在该子图形的顶点上运行DFS时,我们将找到连接的顶点,并且不必在下一次运行DFS时考虑这些 . 因此,为每个顶点运行的可能性是不正确的 .
根据Cormen et al., Introduction to Algorithms(CLRS)的引理22.11:
这在几个答案中已经提到过;在这里,我还将提供基于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
子句,用于检测周期:请注意,在此示例中,CLRS ' pseudocode is not captured because we'中的
time
仅对检测周期感兴趣 . 还有一些样板代码用于从边列表构建图形的邻接列表表示 .执行此脚本时,它会输出以下输出:
这些正是CLRS图22.4中示例的后沿 .
正如你所说,你有一组工作,需要按一定的顺序执行 .
Topological sort
为您提供了调度作业所需的订单(如果是direct acyclic graph
,则为依赖性问题) . 运行dfs
并维护一个列表,并开始在列表的开头添加节点,如果遇到已访问过的节点 . 然后你在给定的图中找到了一个循环 .如果图表满足此属性
然后图表至少包含循环 .