查找有向图中的所有循环

Question

如何从有向图中找到(迭代)有向图中的所有周期？

例如,我想要这样的东西:

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

但不是:B-> C-> B.

Answer 1

我在搜索中发现了这个页面,因为循环与强连接组件不同,我继续搜索,最后,我找到了一个有效的算法,列出了有向图的所有(基本)周期.它来自Donald B. Johnson,论文可以在以下链接中找到:

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

可以在以下位置找到java实现:

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

一个数学约翰逊的算法演示可以发现这里实现,可以从右边(下载"下载作者码").

注意:实际上,这个问题有很多算法.其中一些列在本文中:

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

根据文章,约翰逊的算法是最快的算法.

Answer 2

使用回溯的深度优先搜索应该在这里工作.保留一个布尔值数组,以跟踪您之前是否访问过某个节点.如果你的新节点用完了(没有点击你已经存在的节点),那么只需回溯并尝试不同的分支.

如果您有一个邻接列表来表示图形,则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;

使用start节点调用上述函数:

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

Answer 3

首先 - 你真的不想尝试找到字面上的所有周期,因为如果有1那么就有无数个.例如ABA,ABABA等.或者可以将2个周期连接到8个周期等等......有意义的方法是寻找所有所谓的简单周期 - 那些不会跨越自己的周期在开始/结束点.然后,如果您希望您可以生成简单循环的组合.

在有向图中查找所有简单循环的基线算法之一是:在图中对所有简单路径(那些不自交的路径)进行深度优先遍历.每当当前节点在堆栈上具有后继节点时,就会发现一个简单的循环.它由堆栈中的元素组成,从标识的后继开始到堆栈顶部结束.所有简单路径的深度优先遍历类似于深度优先搜索,但是您不会将当前在堆栈上的访问节点标记/记录为停止点.

上面的强力算法非常低效,并且除此之外还生成多个循环副本.然而,它是多种实用算法的起点,它们应用各种增强功能以​​提高性能并避免循环重复.前一段时间我很惊讶地发现这些算法在教科书和网络上都不容易获得.所以我做了一些研究,并在开源Java库中的无向图中为循环实现了4个这样的算法和1个算法:http://code.google.com/p/niographs/.

顺便说一句,因为我提到了无向图:那些算法不同.构建生成树,然后不是树的一部分的每个边与树中的一些边形成一个简单的循环.发现这种循环形成了一个所谓的循环基础.然后可以通过组合2个或更多个不同的碱基循环来找到所有简单循环.有关详细信息,请参阅:http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf.

Answer 4

我发现解决这个问题的最简单的选择是使用被调用的python lib networkx.

它实现了在这个问题的最佳答案中提到的约翰逊算法,但它的执行非常简单.

简而言之,您需要以下内容:

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']]

Answer 5

澄清:

1. 强连接组件将查找其中至少有一个循环的所有子图,而不是图中所有可能的循环.例如,如果你采用所有强连接组件并将它们中的每一个折叠/分组/合并为一个节点(即每个组件的一个节点),你将获得一个没有循环的树(实际上是一个DAG).每个组件(基本上是一个至少有一个循环的子图)可以在内部包含更多可能的循环,因此SCC将找不到所有可能的循环,它将找到至少有一个循环的所有可能组,如果您组他们,然后图表将没有周期.

2. 如同其他人提到的那样,在图中找到所有简单周期,约翰逊的算法是一个候选者.

Answer 6

具有后边缘的基于 DFS 的变体确实会找到循环，但在许多情况下，它不会是最小循环。一般来说，DFS 会给你一个标志，表明存在一个循环，但它不足以实际找到循环。例如，想象 5 个不同的循环共享两条边。仅使用 DFS（包括回溯变体）没有简单的方法来识别周期。

Johnson 算法确实给出了所有唯一的简单循环，并且具有良好的时间和空间复杂度。

但是，如果您只想找到最小循环（意味着可能有多个循环通过任何顶点并且我们有兴趣找到最小循环）并且您的图不是很大，您可以尝试使用下面的简单方法。与约翰逊的相比，它非常简单但相当慢。

因此，找到 MINIMAL 循环的绝对最简单的方法之一是使用 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

Answer 7

从节点 X 开始并检查所有子节点（如果无向，父节点和子节点是等效的）。将这些子节点标记为 X 的子节点。从任何此类子节点 A 中，将其标记为 A、X' 的子节点，其中 X' 被标记为距离 2 步。）。如果您稍后点击 X 并将其标记为 X'' 的子级，则意味着 X 处于 3 节点循环中。回溯到它的父级很容易（按原样，该算法不支持此操作，因此您会找到具有 X' 的父级）。

注意：如果图是无向的或具有任何双向边，则该算法会变得更加复杂，假设您不想在一个循环中两次遍历同一条边。