查找有向图中的所有循环

发布于 2024-07-13 10:55:07 字数 148 浏览 8 评论 0原文

如何找到(迭代)有向图中往返给定节点的所有循环?

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

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

但不是: B->C->B

How can I find (iterate over) ALL the cycles in a directed graph from/to a given node?

For example, I want something like this:

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

but not:
B->C->B

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(17

吾家有女初长成 2024-07-20 10:55:07

我在搜索中找到了此页面,由于循环与强连通分量不同,我继续搜索,最后,我找到了一种有效的算法,它列出了有向图的所有(基本)循环。 它来自 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

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

I found this page in my search and since cycles are not same as strongly connected components, I kept on searching and finally, I found an efficient algorithm which lists all (elementary) cycles of a directed graph. It is from Donald B. Johnson and the paper can be found in the following link:

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

A java implementation can be found in:

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

A Mathematica demonstration of Johnson's algorithm can be found here, implementation can be downloaded from the right ("Download author code").

Note: Actually, there are many algorithms for this problem. Some of them are listed in this article:

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

According to the article, Johnson's algorithm is the fastest one.

写下不归期 2024-07-20 10:55:07

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

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

Depth first search with backtracking should work here.
Keep an array of boolean values to keep track of whether you visited a node before. If you run out of new nodes to go to (without hitting a node you have already been), then just backtrack and try a different branch.

The DFS is easy to implement if you have an adjacency list to represent the graph. For example adj[A] = {B,C} indicates that B and C are the children of A.

For example, pseudo-code below. "start" is the node you start from.

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;

Call the above function with the start node:

visited = {}
dfs(adj,start,visited)
稚然 2024-07-20 10:55:07

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

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

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

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

< a href="https://i.sstatic.net/tXkt2.png" rel="noreferrer">在此处输入图像描述

The simplest choice I found to solve this problem was using the python lib called networkx.

It implements the Johnson's algorithm mentioned in the best answer of this question but it makes quite simple to execute.

In short you need the following:

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))

Answer: [['a', 'b', 'd', 'e'], ['a', 'b', 'c']]

enter image description here

德意的啸 2024-07-20 10:55:07

首先 - 你并不是真的想尝试找到所有的循环,因为如果有 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

First of all - you do not really want to try find literally all cycles because if there is 1 then there is an infinite number of those. For example A-B-A, A-B-A-B-A etc. Or it may be possible to join together 2 cycles into an 8-like cycle etc., etc... The meaningful approach is to look for all so called simple cycles - those that do not cross themselves except in the start/end point. Then if you wish you can generate combinations of simple cycles.

One of the baseline algorithms for finding all simple cycles in a directed graph is this: Do a depth-first traversal of all simple paths (those that do not cross themselves) in the graph. Every time when the current node has a successor on the stack a simple cycle is discovered. It consists of the elements on the stack starting with the identified successor and ending with the top of the stack. Depth first traversal of all simple paths is similar to depth first search but you do not mark/record visited nodes other than those currently on the stack as stop points.

The brute force algorithm above is terribly inefficient and in addition to that generates multiple copies of the cycles. It is however the starting point of multiple practical algorithms which apply various enhancements in order to improve performance and avoid cycle duplication. I was surprised to find out some time ago that these algorithms are not readily available in textbooks and on the web. So I did some research and implemented 4 such algorithms and 1 algorithm for cycles in undirected graphs in an open source Java library here : http://code.google.com/p/niographs/ .

BTW, since I mentioned undirected graphs : The algorithm for those is different. Build a spanning tree and then every edge which is not part of the tree forms a simple cycle together with some edges in the tree. The cycles found this way form a so called cycle base. All simple cycles can then be found by combining 2 or more distinct base cycles. For more details see e.g. this : http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf .

依 靠 2024-07-20 10:55:07

具有后沿的基于 DFS 的变体确实会找到循环,但在许多情况下,它不会是最小循环。 一般来说,DFS 会给出存在循环的标志,但它不足以真正找到循环。 例如,想象 5 个不同的循环共享两条边。 没有简单的方法可以仅使用 DFS(包括回溯变体)来识别循环。

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

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

因此,找到最小循环的绝对最简单的方法之一是使用弗洛伊德算法使用邻接矩阵来查找所有顶点之间的最小路径。
该算法远不如 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

The DFS-based variants with back edges will find cycles indeed, but in many cases it will NOT be minimal cycles. In general DFS gives you the flag that there is a cycle but it is not good enough to actually find cycles. For example, imagine 5 different cycles sharing two edges. There is no simple way to identify cycles using just DFS (including backtracking variants).

Johnson's algorithm is indeed gives all unique simple cycles and has good time and space complexity.

But if you want to just find MINIMAL cycles (meaning that there may be more then one cycle going through any vertex and we are interested in finding minimal ones) AND your graph is not very large, you can try to use the simple method below.
It is VERY simple but rather slow compared to Johnson's.

So, one of the absolutely easiest way to find MINIMAL cycles is to use Floyd's algorithm to find minimal paths between all the vertices using adjacency matrix.
This algorithm is nowhere near as optimal as Johnson's, but it is so simple and its inner loop is so tight that for smaller graphs (<=50-100 nodes) it absolutely makes sense to use it.
Time complexity is O(n^3), space complexity O(n^2) if you use parent tracking and O(1) if you don't.
First of all let's find the answer to the question if there is a cycle.
The algorithm is dead-simple. Below is snippet in 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
      }
    }
  }

Originally this algorithm operates on weighted-edge graph to find all shortest paths between all pairs of nodes (hence the weights argument). For it to work correctly you need to provide 1 if there is a directed edge between the nodes or NO_EDGE otherwise.
After algorithm executes, you can check the main diagonal, if there are values less then NO_EDGE than this node participates in a cycle of length equal to the value. Every other node of the same cycle will have the same value (on the main diagonal).

To reconstruct the cycle itself we need to use slightly modified version of algorithm with parent tracking.

  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
      }
    }
  }

Parents matrix initially should contain source vertex index in an edge cell if there is an edge between the vertices and -1 otherwise.
After function returns, for each edge you will have reference to the parent node in the shortest path tree.
And then it's easy to recover actual cycles.

All in all we have the following program to find all minimal cycles

  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
  }

and a small main method just to test the result

  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")
  }

and the output is

The following minimal cycle found:
012
Total: 1 cycle found
英雄似剑 2024-07-20 10:55:07

澄清一下:

  1. 强连通分量将找到其中至少有一个循环的所有子图,而不是图中所有可能的循环。 例如,如果您将所有强连接组件折叠/分组/合并为一个节点(即每个组件一个节点),您将得到一棵没有循环的树(实际上是 DAG)。 每个组件(基本上是一个至少有一个循环的子图)内部可以包含更多可能的循环,因此 SCC 不会找到所有可能的循环,它会找到至少有一个循环的所有可能的组,并且如果您分组他们,那么该图将不会有环。

  2. 要找到图中的所有个简单循环,正如其他人提到的,约翰逊算法是一个候选算法。

To clarify:

  1. Strongly Connected Components will find all subgraphs that have at least one cycle in them, not all possible cycles in the graph. e.g. if you take all strongly connected components and collapse/group/merge each one of them into one node (i.e. a node per component), you'll get a tree with no cycles (a DAG actually). Each component (which is basically a subgraph with at least one cycle in it) can contain many more possible cycles internally, so SCC will NOT find all possible cycles, it will find all possible groups that have at least one cycle, and if you group them, then the graph will not have cycles.

  2. to find all simple cycles in a graph, as others mentioned, Johnson's algorithm is a candidate.

苍风燃霜 2024-07-20 10:55:07

我曾经被问过这个问题,我怀疑你也遇到过这种情况,你来这里是为了寻求帮助。 把问题分成三个问题,就变得容易了。

  1. 你如何确定下一个有效的
    路线
  2. 如何确定一个点是否有
    已被使用,
  3. 你如何避免跨越
    同样的

问题1)
使用迭代器模式提供迭代路由结果的方法。 放置获取下一条路线的逻辑的好地方可能是迭代器的“moveNext”。 要找到有效的路线,这取决于您的数据结构。 对我来说,这是一个充满有效路线可能性的 SQL 表,因此我必须构建一个查询来获取给定源的有效目的地。

问题2)
当你找到它们时,将每个节点推送到一个集合中,这意味着你可以通过询问你正在动态构建的集合来很容易地看到你是否在某个点上“双倍返回”。

问题3)
如果在任何时候您发现自己正在加倍返回,则可以从集合中取出内容并“备份”。 然后从那时起尝试再次“前进”。

Hack:如果您使用 Sql Server 2008,如果您在树中构建数据,则可以使用一些新的“层次结构”来快速解决此问题。

I was given this as an interview question once, I suspect this has happened to you and you are coming here for help. Break the problem into three questions and it becomes easier.

  1. how do you determine the next valid
    route
  2. how do you determine if a point has
    been used
  3. how do you avoid crossing over the
    same point again

Problem 1)
Use the iterator pattern to provide a way of iterating route results. A good place to put the logic to get the next route is probably the "moveNext" of your iterator. To find a valid route, it depends on your data structure. For me it was a sql table full of valid route possibilities so I had to build a query to get the valid destinations given a source.

Problem 2)
Push each node as you find them into a collection as you get them, this means that you can see if you are "doubling back" over a point very easily by interrogating the collection you are building on the fly.

Problem 3)
If at any point you see you are doubling back, you can pop things off the collection and "back up". Then from that point try to "move forward" again.

Hack: if you are using Sql Server 2008 there is are some new "hierarchy" things you can use to quickly solve this if you structure your data in a tree.

雨后彩虹 2024-07-20 10:55:07

无向图而言,最近发表的一篇论文(无向图中的循环和 st 路径的最优列表)提供了渐近最优解。 您可以在这里阅读http://arxiv.org/abs/1205.2766 或在这里http://dl.acm.org/itation.cfm?id=2627951
我知道它不能回答你的问题,但由于你的问题的标题没有提到方向,它可能对谷歌搜索仍然有用

In the case of undirected graph, a paper recently published (Optimal listing of cycles and st-paths in undirected graphs) offers an asymptotically optimal solution. You can read it here http://arxiv.org/abs/1205.2766 or here http://dl.acm.org/citation.cfm?id=2627951
I know it doesn't answer your question, but since the title of your question doesn't mention direction, it might still be useful for Google search

心意如水 2024-07-20 10:55:07

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

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

Start at node X and check for all child nodes (parent and child nodes are equivalent if undirected). Mark those child nodes as being children of X. From any such child node A, mark it's children of being children of A, X', where X' is marked as being 2 steps away.). If you later hit X and mark it as being a child of X'', that means X is in a 3 node cycle. Backtracking to it's parent is easy (as-is, the algorithm has no support for this so you'd find whichever parent has X').

Note: If graph is undirected or has any bidirectional edges, this algorithm gets more complicated, assuming you don't want to traverse the same edge twice for a cycle.

戈亓 2024-07-20 10:55:07

如果您想要找到图中的所有基本电路,您可以使用 JAMES C. TIERNAN 的 EC 算法,该算法在 1970 年以来的一篇论文中找到。

我设法实现的非常原始 EC 算法它在 php 中(希望没有错误,如下所示)。 如果有的话它也可以找到循环。 此实现中的电路(尝试克隆原始电路)是非零元素。 这里的零代表不存在(我们所知的 null)。

除此之外,下面还有一个使算法更加独立的实现,这意味着节点可以从任何地方开始,甚至可以从负数开始,例如-4,-3,-2,..等。

在这两种情况下都需要节点是连续的。

您可能需要研究原始论文,James C. Tiernan Elementary Circuit Algorithm

<?php
echo  "<pre><br><br>";

$G = array(
        1=>array(1,2,3),
        2=>array(1,2,3),
        3=>array(1,2,3)
);


define('N',key(array_slice($G, -1, 1, true)));
$P = array(1=>0,2=>0,3=>0,4=>0,5=>0);
$H = array(1=>$P, 2=>$P, 3=>$P, 4=>$P, 5=>$P );
$k = 1;
$P[$k] = key($G);
$Circ = array();


#[Path Extension]
EC2_Path_Extension:
foreach($G[$P[$k]] as $j => $child ){
    if( $child>$P[1] and in_array($child, $P)===false and in_array($child, $H[$P[$k]])===false ){
    $k++;
    $P[$k] = $child;
    goto EC2_Path_Extension;
}   }

#[EC3 Circuit Confirmation]
if( in_array($P[1], $G[$P[$k]])===true ){//if PATH[1] is not child of PATH[current] then don't have a cycle
    $Circ[] = $P;
}

#[EC4 Vertex Closure]
if($k===1){
    goto EC5_Advance_Initial_Vertex;
}
//afou den ksana theoreitai einai asfales na svisoume
for( $m=1; $m<=N; $m++){//H[P[k], m] <- O, m = 1, 2, . . . , N
    if( $H[$P[$k-1]][$m]===0 ){
        $H[$P[$k-1]][$m]=$P[$k];
        break(1);
    }
}
for( $m=1; $m<=N; $m++ ){//H[P[k], m] <- O, m = 1, 2, . . . , N
    $H[$P[$k]][$m]=0;
}
$P[$k]=0;
$k--;
goto EC2_Path_Extension;

#[EC5 Advance Initial Vertex]
EC5_Advance_Initial_Vertex:
if($P[1] === N){
    goto EC6_Terminate;
}
$P[1]++;
$k=1;
$H=array(
        1=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        2=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        3=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        4=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        5=>array(1=>0,2=>0,3=>0,4=>0,5=>0)
);
goto EC2_Path_Extension;

#[EC5 Advance Initial Vertex]
EC6_Terminate:
print_r($Circ);
?>

那么这是另一种实现,更独立于图,没有 goto 也没有数组值,而是使用数组键,路径,图形和电路存储为数组键(如果您愿意,可以使用数组值,只需更改所需的行)。 示例图从-4开始以显示其独立性。

<?php

$G = array(
        -4=>array(-4=>true,-3=>true,-2=>true),
        -3=>array(-4=>true,-3=>true,-2=>true),
        -2=>array(-4=>true,-3=>true,-2=>true)
);


$C = array();


EC($G,$C);
echo "<pre>";
print_r($C);
function EC($G, &$C){

    $CNST_not_closed =  false;                          // this flag indicates no closure
    $CNST_closed        = true;                         // this flag indicates closure
    // define the state where there is no closures for some node
    $tmp_first_node  =  key($G);                        // first node = first key
    $tmp_last_node  =   $tmp_first_node-1+count($G);    // last node  = last  key
    $CNST_closure_reset = array();
    for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){
        $CNST_closure_reset[$k] = $CNST_not_closed;
    }
    // define the state where there is no closure for all nodes
    for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){
        $H[$k] = $CNST_closure_reset;   // Key in the closure arrays represent nodes
    }
    unset($tmp_first_node);
    unset($tmp_last_node);


    # Start algorithm
    foreach($G as $init_node => $children){#[Jump to initial node set]
        #[Initial Node Set]
        $P = array();                   // declare at starup, remove the old $init_node from path on loop
        $P[$init_node]=true;            // the first key in P is always the new initial node
        $k=$init_node;                  // update the current node
                                        // On loop H[old_init_node] is not cleared cause is never checked again
        do{#Path 1,3,7,4 jump here to extend father 7
            do{#Path from 1,3,8,5 became 2,4,8,5,6 jump here to extend child 6
                $new_expansion = false;
                foreach( $G[$k] as $child => $foo ){#Consider each child of 7 or 6
                    if( $child>$init_node and isset($P[$child])===false and $H[$k][$child]===$CNST_not_closed ){
                        $P[$child]=true;    // add this child to the path
                        $k = $child;        // update the current node
                        $new_expansion=true;// set the flag for expanding the child of k
                        break(1);           // we are done, one child at a time
            }   }   }while(($new_expansion===true));// Do while a new child has been added to the path

            # If the first node is child of the last we have a circuit
            if( isset($G[$k][$init_node])===true ){
                $C[] = $P;  // Leaving this out of closure will catch loops to
            }

            # Closure
            if($k>$init_node){                  //if k>init_node then alwaya count(P)>1, so proceed to closure
                $new_expansion=true;            // $new_expansion is never true, set true to expand father of k
                unset($P[$k]);                  // remove k from path
                end($P); $k_father = key($P);   // get father of k
                $H[$k_father][$k]=$CNST_closed; // mark k as closed
                $H[$k] = $CNST_closure_reset;   // reset k closure
                $k = $k_father;                 // update k
        }   } while($new_expansion===true);//if we don't wnter the if block m has the old k$k_father_old = $k;
        // Advance Initial Vertex Context
    }//foreach initial


}//function

?>

我已经分析并记录了 EC,但不幸的是该文档是希腊语的。

If what you want is to find all elementary circuits in a graph you can use the EC algorithm, by JAMES C. TIERNAN, found on a paper since 1970.

The very original EC algorithm as I managed to implement it in php (hope there are no mistakes is shown below). It can find loops too if there are any. The circuits in this implementation (that tries to clone the original) are the non zero elements. Zero here stands for non-existence (null as we know it).

Apart from that below follows an other implementation that gives the algorithm more independece, this means the nodes can start from anywhere even from negative numbers, e.g -4,-3,-2,.. etc.

In both cases it is required that the nodes are sequential.

You might need to study the original paper, James C. Tiernan Elementary Circuit Algorithm

<?php
echo  "<pre><br><br>";

$G = array(
        1=>array(1,2,3),
        2=>array(1,2,3),
        3=>array(1,2,3)
);


define('N',key(array_slice($G, -1, 1, true)));
$P = array(1=>0,2=>0,3=>0,4=>0,5=>0);
$H = array(1=>$P, 2=>$P, 3=>$P, 4=>$P, 5=>$P );
$k = 1;
$P[$k] = key($G);
$Circ = array();


#[Path Extension]
EC2_Path_Extension:
foreach($G[$P[$k]] as $j => $child ){
    if( $child>$P[1] and in_array($child, $P)===false and in_array($child, $H[$P[$k]])===false ){
    $k++;
    $P[$k] = $child;
    goto EC2_Path_Extension;
}   }

#[EC3 Circuit Confirmation]
if( in_array($P[1], $G[$P[$k]])===true ){//if PATH[1] is not child of PATH[current] then don't have a cycle
    $Circ[] = $P;
}

#[EC4 Vertex Closure]
if($k===1){
    goto EC5_Advance_Initial_Vertex;
}
//afou den ksana theoreitai einai asfales na svisoume
for( $m=1; $m<=N; $m++){//H[P[k], m] <- O, m = 1, 2, . . . , N
    if( $H[$P[$k-1]][$m]===0 ){
        $H[$P[$k-1]][$m]=$P[$k];
        break(1);
    }
}
for( $m=1; $m<=N; $m++ ){//H[P[k], m] <- O, m = 1, 2, . . . , N
    $H[$P[$k]][$m]=0;
}
$P[$k]=0;
$k--;
goto EC2_Path_Extension;

#[EC5 Advance Initial Vertex]
EC5_Advance_Initial_Vertex:
if($P[1] === N){
    goto EC6_Terminate;
}
$P[1]++;
$k=1;
$H=array(
        1=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        2=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        3=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        4=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        5=>array(1=>0,2=>0,3=>0,4=>0,5=>0)
);
goto EC2_Path_Extension;

#[EC5 Advance Initial Vertex]
EC6_Terminate:
print_r($Circ);
?>

then this is the other implementation, more independent of the graph, without goto and without array values, instead it uses array keys, the path, the graph and circuits are stored as array keys (use array values if you like, just change the required lines). The example graph start from -4 to show its independence.

<?php

$G = array(
        -4=>array(-4=>true,-3=>true,-2=>true),
        -3=>array(-4=>true,-3=>true,-2=>true),
        -2=>array(-4=>true,-3=>true,-2=>true)
);


$C = array();


EC($G,$C);
echo "<pre>";
print_r($C);
function EC($G, &$C){

    $CNST_not_closed =  false;                          // this flag indicates no closure
    $CNST_closed        = true;                         // this flag indicates closure
    // define the state where there is no closures for some node
    $tmp_first_node  =  key($G);                        // first node = first key
    $tmp_last_node  =   $tmp_first_node-1+count($G);    // last node  = last  key
    $CNST_closure_reset = array();
    for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){
        $CNST_closure_reset[$k] = $CNST_not_closed;
    }
    // define the state where there is no closure for all nodes
    for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){
        $H[$k] = $CNST_closure_reset;   // Key in the closure arrays represent nodes
    }
    unset($tmp_first_node);
    unset($tmp_last_node);


    # Start algorithm
    foreach($G as $init_node => $children){#[Jump to initial node set]
        #[Initial Node Set]
        $P = array();                   // declare at starup, remove the old $init_node from path on loop
        $P[$init_node]=true;            // the first key in P is always the new initial node
        $k=$init_node;                  // update the current node
                                        // On loop H[old_init_node] is not cleared cause is never checked again
        do{#Path 1,3,7,4 jump here to extend father 7
            do{#Path from 1,3,8,5 became 2,4,8,5,6 jump here to extend child 6
                $new_expansion = false;
                foreach( $G[$k] as $child => $foo ){#Consider each child of 7 or 6
                    if( $child>$init_node and isset($P[$child])===false and $H[$k][$child]===$CNST_not_closed ){
                        $P[$child]=true;    // add this child to the path
                        $k = $child;        // update the current node
                        $new_expansion=true;// set the flag for expanding the child of k
                        break(1);           // we are done, one child at a time
            }   }   }while(($new_expansion===true));// Do while a new child has been added to the path

            # If the first node is child of the last we have a circuit
            if( isset($G[$k][$init_node])===true ){
                $C[] = $P;  // Leaving this out of closure will catch loops to
            }

            # Closure
            if($k>$init_node){                  //if k>init_node then alwaya count(P)>1, so proceed to closure
                $new_expansion=true;            // $new_expansion is never true, set true to expand father of k
                unset($P[$k]);                  // remove k from path
                end($P); $k_father = key($P);   // get father of k
                $H[$k_father][$k]=$CNST_closed; // mark k as closed
                $H[$k] = $CNST_closure_reset;   // reset k closure
                $k = $k_father;                 // update k
        }   } while($new_expansion===true);//if we don't wnter the if block m has the old k$k_father_old = $k;
        // Advance Initial Vertex Context
    }//foreach initial


}//function

?>

I have analized and documented the EC but unfortunately the documentation is in Greek.

人海汹涌 2024-07-20 10:55:07

查找 DAG 中的所有循环涉及两个步骤(算法)。

第一步是使用 Tarjan 算法找到强连通分量的集合。

  1. 从任意顶点开始。
  2. 从该顶点开始的 DFS。 对于每个节点 x,保留两个数字,dfs_index[x] 和 dfs_lowval[x]。
    dfs_index[x] 存储该节点被访问的时间,而 dfs_lowval[x] = min(dfs_low[k]) 其中
    k 是 x 在 dfs 生成树中不是 x 的直接父代的所有子代。
  3. 具有相同 dfs_lowval[x] 的所有节点都位于同一强连接组件中。

第二步是找到连接组件内的循环(路径)。 我的建议是使用 Hierholzer 算法的修改版本。

这个想法是:

  1. 选择任何起始顶点 v,并沿着从该顶点开始的边轨迹,直到返回到 v。
    不可能卡在除 v 之外的任何顶点,因为所有顶点的偶数度确保了当轨迹进入另一个顶点 w 时,一定有一条未使用的边离开 w。 这样形成的游览是封闭游览,但可能不会覆盖初始图的所有顶点和边。
  2. 只要存在属于当前游览的顶点 v,但其相邻边不是游览的一部分,则从 v 开始另一条路径,沿着未使用的边,直到返回到 v,并将以这种方式形成的游览加入到之前的旅行。

以下是带有测试用例的 Java 实现的链接:

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

There are two steps (algorithms) involved in finding all cycles in a DAG.

The first step is to use Tarjan's algorithm to find the set of strongly connected components.

  1. Start from any arbitrary vertex.
  2. DFS from that vertex. For each node x, keep two numbers, dfs_index[x] and dfs_lowval[x].
    dfs_index[x] stores when that node is visited, while dfs_lowval[x] = min(dfs_low[k]) where
    k is all the children of x that is not the directly parent of x in the dfs-spanning tree.
  3. All nodes with the same dfs_lowval[x] are in the same strongly connected component.

The second step is to find cycles (paths) within the connected components. My suggestion is to use a modified version of Hierholzer's algorithm.

The idea is:

  1. Choose any starting vertex v, and follow a trail of edges from that vertex until you return to v.
    It is not possible to get stuck at any vertex other than v, because the even degree of all vertices ensures that, when the trail enters another vertex w there must be an unused edge leaving w. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.
  2. As long as there exists a vertex v that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from v, following unused edges until you return to v, and join the tour formed in this way to the previous tour.

Here is the link to a Java implementation with a test case:

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

与他有关 2024-07-20 10:55:07

我偶然发现了以下算法,它似乎比约翰逊的算法更有效(至少对于较大的图而言)。 然而,我不确定它与 Tarjan 算法相比的性能。
另外,到目前为止我只检查了三角形。 如果有兴趣,请参阅 Norishige Chiba 和 Takao Nishizeki 的“Arboricity and Subgraph Listing Algorithms” (http://dx .doi.org/10.1137/0214017

I stumbled over the following algorithm which seems to be more efficient than Johnson's algorithm (at least for larger graphs). I am however not sure about its performance compared to Tarjan's algorithm.
Additionally, I only checked it out for triangles so far. If interested, please see "Arboricity and Subgraph Listing Algorithms" by Norishige Chiba and Takao Nishizeki (http://dx.doi.org/10.1137/0214017)

等数载,海棠开 2024-07-20 10:55:07

从起始节点s开始进行DFS,在遍历过程中记录DFS路径,如果在到s的路径中找到从节点v到s的边,则记录该路径。 (v,s) 是 DFS 树中的后沿,因此表示包含 s 的环。

DFS from the start node s, keep track of the DFS path during traversal, and record the path if you find an edge from node v in the path to s. (v,s) is a back-edge in the DFS tree and thus indicates a cycle containing s.

我的鱼塘能养鲲 2024-07-20 10:55:07

关于您关于排列周期的问题,请在此处阅读更多内容:
https://www.codechef.com/problems/PCYCLE

您可以尝试此代码(输入尺寸和位数):

# include<cstdio>
using namespace std;

int main()
{
    int n;
    scanf("%d",&n);

    int num[1000];
    int visited[1000]={0};
    int vindex[2000];
    for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);

    int t_visited=0;
    int cycles=0;
    int start=0, index;

    while(t_visited < n)
    {
        for(int i=1;i<=n;i++)
        {
            if(visited[i]==0)
            {
                vindex[start]=i;
                visited[i]=1;
                t_visited++;
                index=start;
                break;
            }
        }
        while(true)
        {
            index++;
            vindex[index]=num[vindex[index-1]];

            if(vindex[index]==vindex[start])
                break;
            visited[vindex[index]]=1;
            t_visited++;
        }
        vindex[++index]=0;
        start=index+1;
        cycles++;
    }

    printf("%d\n",cycles,vindex[0]);

    for(int i=0;i<(n+2*cycles);i++)
    {
        if(vindex[i]==0)
            printf("\n");
        else
            printf("%d ",vindex[i]);
    }
}

Regarding your question about the Permutation Cycle, read more here:
https://www.codechef.com/problems/PCYCLE

You can try this code (enter the size and the digits number):

# include<cstdio>
using namespace std;

int main()
{
    int n;
    scanf("%d",&n);

    int num[1000];
    int visited[1000]={0};
    int vindex[2000];
    for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);

    int t_visited=0;
    int cycles=0;
    int start=0, index;

    while(t_visited < n)
    {
        for(int i=1;i<=n;i++)
        {
            if(visited[i]==0)
            {
                vindex[start]=i;
                visited[i]=1;
                t_visited++;
                index=start;
                break;
            }
        }
        while(true)
        {
            index++;
            vindex[index]=num[vindex[index-1]];

            if(vindex[index]==vindex[start])
                break;
            visited[vindex[index]]=1;
            t_visited++;
        }
        vindex[++index]=0;
        start=index+1;
        cycles++;
    }

    printf("%d\n",cycles,vindex[0]);

    for(int i=0;i<(n+2*cycles);i++)
    {
        if(vindex[i]==0)
            printf("\n");
        else
            printf("%d ",vindex[i]);
    }
}
梦回旧景 2024-07-20 10:55:07

二楼答案中的伪代码的DFS c++版本:

void findCircleUnit(int start, int v, bool* visited, vector<int>& path) {
    if(visited[v]) {
        if(v == start) {
            for(auto c : path)
                cout << c << " ";
            cout << endl;
            return;
        }
        else 
            return;
    }
    visited[v] = true;
    path.push_back(v);
    for(auto i : G[v])
        findCircleUnit(start, i, visited, path);
    visited[v] = false;
    path.pop_back();
}

DFS c++ version for the pseudo-code in second floor's answer:

void findCircleUnit(int start, int v, bool* visited, vector<int>& path) {
    if(visited[v]) {
        if(v == start) {
            for(auto c : path)
                cout << c << " ";
            cout << endl;
            return;
        }
        else 
            return;
    }
    visited[v] = true;
    path.push_back(v);
    for(auto i : G[v])
        findCircleUnit(start, i, visited, path);
    visited[v] = false;
    path.pop_back();
}
帝王念 2024-07-20 10:55:07

CXXGraph提供了一组用于检测周期的算法和函数。

有关完整的算法说明,请访问 wiki

The CXXGraph library give a set of algorithms and functions to detect cycles.

For a full algorithm explanation visit the wiki.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文