在有向图中找到所有循环

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

#1 楼

我在搜索中找到了该页面，由于循环与强连接的组件并不相同，因此我一直进行搜索，最后找到了一种有效的算法，该算法列出了有向图的所有（基本）循环。它来自唐纳德·B·约翰逊（Donald B. Johnson），可以在以下链接中找到本文：

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

Java实现可在以下位置找到：

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

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

注意：实际上，有很多算法可以解决此问题。本文中列出了其中一些：

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

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

#2 楼

具有回溯功能的深度优先搜索应该在这里起作用。
保留一个布尔值数组，以跟踪您之前是否访问过节点。如果您用完了要去的新节点（没有击中您已经去过的节点），则只需回溯并尝试其他分支即可。

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

例如下面的伪代码。 “开始”是您从中开始的节点。

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)

#3 楼

首先-您真的不想尝试从字面上看所有周期，因为如果有1，那么就有无限多个周期。例如ABA，ABABA等。或者也可以将2个循环连接成一个类似8的循环，以此类推...等等。有意义的方法是寻找所有所谓的简单循环-除自身以外不交叉的循环在起点/终点。然后，如果您希望可以生成简单循环的组合。

用于在有向图中找到所有简单循环的基线算法之一是：对所有简单路径进行深度优先遍历（不要在图中交叉。每当当前节点在堆栈上具有后继者时，都会发现一个简单的周期。它由堆栈中的元素组成，这些元素从已标识的后继者开始，到堆栈顶部为止。所有简单路径的深度优先遍历与深度优先搜索相似，但是除了当前堆栈中的那些节点以外，您不会将访问的节点标记/记录为停止点。

以上的蛮力算法效率极低且除此之外，还会生成循环的多个副本。但是，这是多种实用算法的起点，这些实用算法应用了各种增强功能以​​提高性能并避免循环重复。令我惊讶的是，不久前发现教科书和网络上还没有这些算法。因此，我进行了一些研究，并在开放源Java库的http://code.google.com/p/niographs/中实现了4种这样的算法和1种针对无向图中的循环的算法。http://code.google.com/p/niographs/。

顺便说一句，因为我提到了无向图：那些算法是不同的。生成一棵生成树，然后将不属于树的每个边缘与树中的某些边缘一起形成一个简单的循环。以这种方式发现的循环形成了所谓的循环基础。然后可以通过组合2个或更多个不同的基本周期来找到所有简单周期。有关更多详细信息，请参见：http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf。

#4 楼

我发现解决此问题的最简单选择是使用名为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']]

#5 楼

需要说明的是：


牢固连接的组件将找到所有具有至少一个循环的子图，而不是图中的所有可能循环。例如如果您将所有紧密连接的组件都折叠起来/分组/合并到一个节点（即每个组件一个节点），则会得到一棵没有循环的树（实际上是DAG）。每个组件（基本上是一个其中包含至少一个循环的子图）在内部可以包含更多可能的循环，因此SCC不会找到所有可能的循环，它将找到具有至少一个循环的所有可能的组，并且如果您进行分组它们，那么图形将没有周期。
要找到图中的所有简单循环，正如其他人提到的那样，约翰逊算法是一种候选方法。

#6 楼

具有后边缘的基于DFS的变体确实会找到循环，但是在许多情况下，它并不是最小的循环。通常，DFS会为您提供一个标记，表明存在一个循环，但不足以实际找到循环。例如，假设5个不同的周期共享两个边。没有简单的方法仅使用DFS（包括回溯变体）来识别周期。

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

但是，如果您只想找到最小周期（意味着可能有一个以上的周期遍历任何顶点，而我们有兴趣寻找最小顶点）并且您的图形不是很大，则可以尝试使用以下简单方法。
与Johnson的相比，它非常简单，但速度却很慢。

因此，找到最小周期的绝对最简单的方法之一是使用Floyd算法使用邻接关系在所有顶点之间找到最小路径。
该算法远没有强森算法最佳，但它是如此简单，其内部循环是如此紧密，以至于对于较小的图（<= 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
      }
    }
  }

该算法最初在加权边图上运行，以查找所有节点对之间的所有最短路径（因此，使用weights参数）。为使其正常工作，如果节点之间有定向边，则需要提供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

#7 楼

曾经有人问我这是面试问题，我怀疑这已经发生在您身上，您正在这里寻求帮助。将问题分为三个问题，变得更容易。


如何确定下一条有效路线

如何确定点是否具有
开始使用
如何避免再次越过
相同的点

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

问题2）
在找到每个节点时将其推入当您将它们添加到集合中时，这意味着您可以通过查询正在构建的集合来非常轻松地查看是否要在某个点上“加倍返回”。

问题3）
如果在任何时候看到要翻倍，都可以从集合中弹出东西并“备份”。然后从这一点开始尝试再次“前进”。

hack：如果您使用的是Sql Server 2008，则在构建数据时可以使用一些新的“层次结构”来快速解决此问题。在树上。

#8 楼

对于无向图，最近发表的一篇论文（无向图中的循环和st路径的最佳列表）提供了一种渐近最优解。您可以在http://arxiv.org/abs/1205.2766或http://dl.acm.org/citation.cfm?id=2627951
上阅读它，我知道它不能回答您的问题，但是由于您的问题的标题未提及方向，因此它可能仍对Google搜索有用

#9 楼

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

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

#10 楼

如果要在图形中查找所有基本电路，可以使用JAMES C. TIERNAN的EC算法，该算法自1970年以来在纸上发现。

我设法实现了非常原始的EC算法在php中实现它（希望下面没有错误）。如果有循环，它也可以找到循环。此实现中的电路（试图克隆原始电路）是非零元素。这里的零代表不存在（我们知道它为空）。

除以下内容外，还有另一个实现使算法更加独立，它意味着节点可以从任何地方开始，甚至从负数开始，例如-4，-3，-2等。

在两种情况下都要求节点是顺序的。

您可能需要研究原始论文James C. Tiernan基本电路算法

<?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，但是不幸的是，该文档使用的是希腊文。

#11 楼

在DAG中查找所有循环涉及两个步骤（算法）。

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


从任意顶点开始。
从该顶点开始DFS。对于每个节点x，保留两个数字dfs_index [x]和dfs_lowval [x]。
dfs_index [x]存储何时访问该节点，而dfs_lowval [x] = min（dfs_low [k]）其中
k是x的所有子代，它们不是dfs生成树中x的直接父代。
所有具有相同dfs_lowval [x]的节点都在同一强连接的组件中。

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

想法是：


选择任何起始顶点v，并跟随该顶点的边缘轨迹，直到返回v。
不可能卡在v以外的任何顶点上，因为所有顶点的偶数度确保了，当轨迹进入另一个顶点w时，必须有一个未使用的边离开w。以这种方式形成的游览是封闭的游览，但可能不会覆盖初始图的所有顶点和边。
只要存在属于当前游览的顶点v但相邻边不属于该部分在游览中，从v开始另一条足迹，沿着未使用的边沿直到您返回v，然后将以这种方式形成的游览加入上一个游览。

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

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

#12 楼

http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf

#13 楼

我偶然发现了以下算法，该算法似乎比约翰逊算法更有效（至少对于较大的图而言）。但是，与Tarjan算法相比，我不确定它的性能。
此外，到目前为止，我只检查了三角形。如果有兴趣，请参阅Norishige Chiba和Takao Nishizeki的“树状图和子图列出算法”（http://dx.doi.org/10.1137/0214017）

#14 楼

从起始节点s开始的DFS，在遍历期间跟踪DFS路径，如果在到s的路径中找到节点v的边缘，则记录该路径。 （v，s）是DFS树中的后端，因此指示包含s的循环。

#15 楼

关于置换周期的问题，请在此处阅读更多信息：
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]);
    }
}

#16 楼

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();
}