识别依赖图中的循环

Question

我正在开发一个名为 ActiveTouch 的 gem。它用于创建复杂的触摸或缓存失效网络。目前，我正在尝试确定一种识别网络中环路的方法。

依赖关系映射的简化版本是一个散列，其中键代表模型，值代表接触的模型。

例如

{ 
  A => [B, C],
  B => [D, F],
  D => [A]
}

在这个例子中我们可以看到A和D之间存在依赖循环，A->B->D->A或者D->A->B->D

为了确定循环，我需要查看所有可能的路径。我怎样才能看到所有可能的路径，像这样：

[
  [A, B, D, A],
  [A, B, F],
  [A, C],
  ...
  [D, A, B, D]
]

Ruby 中的回复会很好，但任何语言都足够了。

Answer 1

基本上你的问题归结为在图中找到一个循环。

您已经将图表存储在此处，作为 adjacency list representation. Detecting cycles is a standard procedure and can be done with a DFS 算法。你从一些顶点和运行 DFS 开始，直到你会看到一些顶点两次。

如果您有断开连接的图形，则对所有组件执行此操作。

Identify Loops Within Dependency Map