在有向图中查找所有环路

Question

在有向图中查找所有环路

233

如何找到（遍历）从/到给定节点的有向图中的所有环？

例如，我想要像这样的东西：

A->B->A
A->B->C->A

但不包括： B->C->B

- user7305

1

作业吧？http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf 不是说这不是一个有效的问题 :) - ShuggyCoUk

7

请注意，这至少是NP困难问题，可能是PSPACE级别的，我得再想想，但现在对于复杂性理论来说还太早了 B-) - Brian Postow

2

如果您的输入图有v个顶点和e条边，则有2 ^（e-v +1）-1个不同的循环（虽然不一定都是简单循环）。那相当多 - 您可能不想明确地编写它们中的所有内容。此外，由于输出大小是指数级别的，算法的复杂度无法为多项式。我认为这个问题还没有答案。 - CygnusX1

1

我最好的选择是这个：http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm - Melsi

1

可能是在有向图中检测循环的最佳算法的重复问题。 - StayOnTarget

显示剩余4条评论

17个回答

46

可以使用深度优先搜索（DFS）和回溯来解决这个问题。使用一个布尔值的数组来记录是否已经访问过某个节点。如果在没有遇到已经访问过的节点的情况下不能找到新的节点，则回溯并尝试不同的分支。

如果有邻接表表示图，则很容易实现DFS。例如，adj[A] = {B，C}表示B和C是A的子节点。

下面是伪代码示例。 "start" 是您从中开始的节点。

dfs(adj,node,visited):  
  if (visited[node]):  
    if (node == start):  
      "found a path"  
    return;  
  visited[node]=YES;  
  for child in adj[node]:  
    dfs(adj,child,visited)
  visited[node]=NO;

使用起始节点调用上述函数：

visited = {}
dfs(adj,start,visited)

- DasBoot

3

谢谢。我更喜欢这种方法，因为它更简单易懂，时间复杂度也合理，虽然可能不是最优的。 - redcalx

6

这如何找到所有的循环？ - brain storm

4

如果（node == start）：在第一次调用中，“node”和“start”是什么？ - brain storm

4

这似乎是找到涉及给定顶点（即“开始”）的所有循环。它从该顶点开始进行深度优先搜索，直到再次返回该顶点，然后它就知道找到了一个循环。但它实际上并没有输出循环本身，只输出它们的数量（但将其修改以输出循环本身并不应该太困难）。 - Bernhard Barker

1

@user1988876 嗯，它只会打印“找到一条路径”的次数等于找到的循环次数（这可以很容易地被计数替代）。是的，它只会从“start”检测到循环。你不需要清除已访问标志，因为每个已访问标志都将由“visited[node]=NO;”清除。但请记住，如果你有一个循环“A->B->C->A”，你会检测到它3次，因为“start”可以是其中的任意3个。一个防止这种情况的想法是有另一个已访问数组，在这个数组中，每个节点在某个时刻都是“start”节点，并且你不会重新访问这些节点。 - Bernhard Barker

显示剩余4条评论

31

我发现解决这个问题最简单的选择是使用名为networkx的Python库。

它实现了在这个问题的最佳答案中提到的 Johnson 算法，但执行起来非常简单。

简而言之，你需要以下内容：

import networkx as nx
import matplotlib.pyplot as plt

# Create Directed Graph
G=nx.DiGraph()

# Add a list of nodes:
G.add_nodes_from(["a","b","c","d","e"])

# Add a list of edges:
G.add_edges_from([("a","b"),("b","c"), ("c","a"), ("b","d"), ("d","e"), ("e","a")])

#Return a list of cycles described as a list o nodes
list(nx.simple_cycles(G))

答案： [['a', 'b', 'd', 'e'], ['a', 'b', 'c']]

- fernandosjp

3

你也可以将字典转换为NetworkX图形：nx.DiGraph({'a': ['b'], 'b': ['c','d'], 'c': ['a'], 'd': ['e'], 'e':['a']})。 - Luke Miles

1

我该如何指定起始顶点？ - nosense

30

首先，你不真正想尝试找到所有循环，因为如果有一个循环，那么就有无数个循环。例如A-B-A，A-B-A-B-A等。或者可能将2个循环连接成8字形的循环等等... 有意义的方法是寻找所有所谓的简单循环-除了起点/终点之外，它们不会交叉。然后，如果需要，可以生成简单循环的组合。

在有向图中查找所有简单循环的基线算法之一是：对图中所有简单路径（即不交叉的路径）进行深度优先遍历。每次当前节点在栈上有一个后继时，就会发现一个简单循环。它由从已识别的后继开始并以堆栈顶部结束的元素组成。所有简单路径的深度优先遍历类似于深度优先搜索，但您不会标记/记录除堆栈上当前节点以外的访问过的节点作为停止点。

上述暴力算法极其低效，并且除此之外还会生成多个循环的副本。但是，它是多种实用算法的起点，这些算法应用各种增强措施以提高性能并避免循环重复。我曾经惊讶地发现，这些算法在教科书和网络上都不容易找到。因此，我研究并在此处的开源Java库中实现了4个这样的算法以及用于无向图中循环的1个算法：http://code.google.com/p/niographs/。

顺便提一下，既然我提到了无向图：这些算法是不同的。首先建立一个生成树，然后那些不在生成树中的边就会和树上的一些边形成一个简单的环。通过这种方式找到的环被称为循环基底。所有简单的环都可以通过组合两个或更多不同的基底环来找到。更多细节请参见此处：http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf。

- Nikolay Ognyanov

作为如何使用 jgrapht 的示例，它被用在 http://code.google.com/p/niographs/ 中。您可以从 https://github.com/jgrapht/jgrapht/wiki/DirectedGraphDemo 中获取示例。 - Vishrant

8

带有回边的基于DFS的变体确实会找到环，但在许多情况下它并不是最小的环。一般来说，DFS只能告诉你是否存在环，但无法实际找到环。例如，想象一下5个不同的环共享两条边。仅使用DFS（包括回溯变体），没有简单的方法来识别环。

Johnson算法确实可以提供所有唯一的简单环，并且具有良好的时间和空间复杂度。

但是，如果您只想找到最小的环（意味着可能有多个环通过任何顶点，我们有兴趣找到最小的那些），而且您的图不是很大，则可以尝试使用下面的简单方法。它非常简单，但与Johnson相比速度要慢得多。

因此，找到最小环的绝对最简单的方法之一是使用Floyd算法使用邻接矩阵查找所有顶点之间的最短路径。该算法远不及Johnson优化，但是对于较小的图（<=50-100个节点），它非常简单，其内部循环非常紧凑，因此绝对有意义使用它。时间复杂度为O(n^3)，空间复杂度为O(n^2)（如果使用父级跟踪）并且为O(1)（如果不使用）。首先，让我们找到问题的答案，即是否存在环。该算法非常简单。以下是Scala代码片段。

  val NO_EDGE = Integer.MAX_VALUE / 2

  def shortestPath(weights: Array[Array[Int]]) = {
    for (k <- weights.indices;
         i <- weights.indices;
         j <- weights.indices) {
      val throughK = weights(i)(k) + weights(k)(j)
      if (throughK < weights(i)(j)) {
        weights(i)(j) = throughK
      }
    }
  }

这个算法最初是在加权边图上操作，以查找所有节点对之间的最短路径（因此需要权重参数）。为了使它正确工作，如果两个节点之间有一个有向边，则需要提供1，否则提供NO_EDGE。

算法执行后，您可以检查主对角线，如果有小于NO_EDGE的值，则此节点参与长度等于该值的循环。同一循环中的其他节点将具有相同的值（在主对角线上）。

要重建循环本身，我们需要使用稍微修改过的带父级跟踪版本的算法。

  def shortestPath(weights: Array[Array[Int]], parents: Array[Array[Int]]) = {
    for (k <- weights.indices;
         i <- weights.indices;
         j <- weights.indices) {
      val throughK = weights(i)(k) + weights(k)(j)
      if (throughK < weights(i)(j)) {
        parents(i)(j) = k
        weights(i)(j) = throughK
      }
    }
  }

如果两个顶点之间有边，则父矩阵的初始值应为源顶点索引，否则为-1。

函数返回后，对于每条边，您将拥有指向最短路径树中父节点的引用。

然后就可以轻松恢复实际的循环。

总之，我们有以下程序查找所有最小循环：

  val NO_EDGE = Integer.MAX_VALUE / 2;

  def shortestPathWithParentTracking(
         weights: Array[Array[Int]],
         parents: Array[Array[Int]]) = {
    for (k <- weights.indices;
         i <- weights.indices;
         j <- weights.indices) {
      val throughK = weights(i)(k) + weights(k)(j)
      if (throughK < weights(i)(j)) {
        parents(i)(j) = parents(i)(k)
        weights(i)(j) = throughK
      }
    }
  }

  def recoverCycles(
         cycleNodes: Seq[Int], 
         parents: Array[Array[Int]]): Set[Seq[Int]] = {
    val res = new mutable.HashSet[Seq[Int]]()
    for (node <- cycleNodes) {
      var cycle = new mutable.ArrayBuffer[Int]()
      cycle += node
      var other = parents(node)(node)
      do {
        cycle += other
        other = parents(other)(node)
      } while(other != node)
      res += cycle.sorted
    }
    res.toSet
  }

还需要一个小的主方法来测试结果

  def main(args: Array[String]): Unit = {
    val n = 3
    val weights = Array(Array(NO_EDGE, 1, NO_EDGE), Array(NO_EDGE, NO_EDGE, 1), Array(1, NO_EDGE, NO_EDGE))
    val parents = Array(Array(-1, 1, -1), Array(-1, -1, 2), Array(0, -1, -1))
    shortestPathWithParentTracking(weights, parents)
    val cycleNodes = parents.indices.filter(i => parents(i)(i) < NO_EDGE)
    val cycles: Set[Seq[Int]] = recoverCycles(cycleNodes, parents)
    println("The following minimal cycle found:")
    cycles.foreach(c => println(c.mkString))
    println(s"Total: ${cycles.size} cycle found")
  }

输出结果为：

The following minimal cycle found:
012
Total: 1 cycle found

- Kirill Frolov

5

澄清一下：

强连通分量将查找所有至少存在一个循环的子图，而不是图中所有可能的循环。例如，如果您将所有强连通分量合并为一个节点（即每个组件一个节点），则可以获得没有循环的树（实际上是有向无环图）。每个组件（基本上是至少包含一个循环的子图）内部可以包含更多可能的循环，因此SCC将不会查找到所有可能的循环，它将查找所有可能具有至少一个循环的组，并且如果将它们合并，则该图将不会有循环。
要找到图中所有简单循环，正如其他人所提到的，Johnson算法就是一个候选算法。

- Eran Medan

3

我曾经在面试中遇到过这个问题，我猜想你也遇到了这个问题并来这里寻求帮助。将问题分解为三个问题，就变得更容易了。

1. 如何确定下一个有效路径 2. 如何确定点是否已被使用 3. 如何避免重复穿越同一点

问题1）使用迭代器模式提供一种迭代路线结果的方法。可能将获取下一个路线的逻辑放在迭代器的“moveNext”中是一个好地方。要找到有效的路径，取决于您的数据结构。对我来说，它是一个充满有效路线可能性的sql表，因此我必须建立一个查询以获取给定源的有效目的地。

问题2）当您发现节点时，将每个节点推入集合中，这意味着您可以通过实时查询正在构建的集合轻松查看是否“回头”超过了一个点。

问题3）如果您在任何时候看到您正在重复穿越，请弹出集合中的事物并“后退”。然后从那个点再次尝试“前进”。

技巧：如果您使用Sql Server 2008，则可以使用一些新的“层次结构”功能来快速解决此问题，如果您将数据结构化为树形结构。

- slf

2

在无向图的情况下，最近发表的一篇论文（《无向图中环和st路径的最优列举》）提供了一种渐进最优解决方案。你可以在这里阅读它：http://arxiv.org/abs/1205.2766 或者在这里：http://dl.acm.org/citation.cfm?id=2627951。尽管这并没有回答你的问题，但是由于你的问题标题中没有提到方向，所以这篇论文可能对谷歌搜索仍然有用。

- daureg

1

在找到有向无环图中所有循环的过程中，涉及两个步骤（算法）。

第一步是使用Tarjan算法来查找强连通组件的集合。

1.从任意顶点开始。 2.从该顶点进行深度优先遍历。对于每个节点x，保留两个数字dfs_index[x]和dfs_lowval[x]。其中，dfs_index[x]存储该节点被访问的时间，而dfs_lowval[x] = min(dfs_low[k])，其中k是x的所有子节点，但不是x在dfs生成树中的直接父节点。 3.所有具有相同dfs_lowval[x]值的节点都在同一个强连通分量中。

第二步是在连接的组件中找到循环（路径）。我的建议是使用修改版的Hierholzer算法。

思路是：

选择任意一个起点v，然后沿着从该顶点开始的边行进，直到回到v。所有顶点的偶度保证了在进入另一个顶点w时不会卡住，因为必定有一条未使用的边离开w。这样形成的旅行路线是闭合的，但可能不覆盖初始图的所有顶点和边。
只要存在一个顶点v属于当前路线，但具有不属于该路线的相邻边，则从v开始另一条路径，按照未使用的边行进，直到回到v，并将以这种方式形成的路径与前一个路径连接起来。

这里是一个带有测试用例的Java实现链接：

http://stones333.blogspot.com/2013/12/find-cycles-in-directed-graph-dag.html

- stones333

21

在有向无环图（DAG）中如何存在环路？ - sky_coder123

这并不能找到所有的循环。 - Vishwa Ratna

1

从节点X开始，检查所有子节点（如果是无向的，则父节点和子节点等效）。将这些子节点标记为X的子节点。对于任何这样的子节点A，将其子节点标记为A的子节点，X'，其中X'被标记为距离2步。如果您稍后遇到X并将其标记为X''的子项，则表示X在3个节点循环中。回溯到其父级很容易（目前算法不支持此功能，因此您需要找到具有X'的任何父级）。

注意：如果图是无向的或具有任何双向边，则该算法变得更加复杂，假设您不希望为了一个循环而两次穿越相同的边。

- Brian

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- eminsenay · Accepted Answer

我在搜索中发现了这个页面，因为循环结构不同于强连通分量，所以我继续搜索，最终找到了一种高效的算法，可以列出有向图中的所有（基本）循环。该算法来自 Donald B. Johnson，文章可以在以下链接中找到：

http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

Java实现可以在以下链接中找到：

http://normalisiert.de/code/java/elementaryCycles.zip

Johnson算法的Mathematica演示可在此处找到，实现可以从右侧下载（“下载作者代码”）。

注意：实际上，对于这个问题有许多算法。其中一些列在这篇文章中：

http://dx.doi.org/10.1137/0205007

根据该文章，Johnson算法是最快的。