我无意中发现了下面的算法，它似乎比Johnson的算法更有效(至少对于更大的图)。然而，与Tarjan的算法相比，我不确定它的性能如何。 此外，到目前为止，我只检查了三角形。如果感兴趣，请参阅千叶Norishige和西泽木高雄(http://dx.doi.org/10.1137/0214017)的“树状性和子图列表算法”

深度优先搜索和回溯应该在这里工作。 保存一个布尔值数组，以跟踪您以前是否访问过某个节点。如果您没有新节点可访问(不涉及已经访问过的节点)，那么只需返回并尝试不同的分支。

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

我曾经在面试中遇到过这样的问题，我怀疑你遇到过这种情况，你来这里寻求帮助。把这个问题分解成三个问题就容易多了。

如何确定下一个有效点 路线 你如何确定一个点是否存在 被使用 你如何避免越过 同样的观点

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

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

问题3) 如果在任何时候你看到你正在折回，你可以从集合中弹出东西并“后退”。然后从这一点开始，再次尝试“前进”。

黑客:如果你正在使用Sql Server 2008，有一些新的“层次结构”的东西，你可以用它来快速解决这个问题，如果你把你的数据结构成树状。

首先，你并不是真的想要找出所有的循环因为如果有1个，那么就会有无穷多个循环。比如A-B-A, A-B-A- b - a等等。或者可以将2个循环组合成一个8-like循环等等……有意义的方法是寻找所有所谓的简单循环——那些除了开始/结束点之外不交叉的循环。如果你愿意，你可以生成简单循环的组合。

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/ .

顺便说一句，因为我提到了无向图:它们的算法是不同的。构建一棵生成树，然后每一条不属于树的边与树中的一些边一起形成一个简单的循环。这样发现的循环形成了所谓的循环基。所有的简单循环都可以通过组合两个或多个不同的基循环来找到。更多细节请参见:http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf。

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

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

除此之外，下面的实现使算法更具独立性，这意味着节点可以从任何地方开始，甚至从负数开始，例如-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，但不幸的是，文档是希腊语。

我在搜索中找到了这个页面，由于循环与强连接组件不相同，我继续搜索，最后，我找到了一个高效的算法，它列出了有向图的所有(基本)循环。这篇论文来自唐纳德·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演示可以在这里找到，实现可以从右边下载(“下载作者代码”)。

注:实际上，这个问题有很多算法。本文列举了其中一些:

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

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