在有向图中查找所有循环

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

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

17 个解决方案

#1

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:

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

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

A java implementation can be found in:

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

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

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

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.

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

#2

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.

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

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

例如,下面的伪代码。 “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;

Call the above function with the start node:

使用start节点调用上面的函数:

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

#3

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.

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

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

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

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

#4

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

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

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

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

#5

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.

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

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

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

#6

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.

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

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.

问题2)当你找到它们时,将每个节点推送到一个集合中,这意味着你可以通过询问你正在构建的集合来查看你是否在一个点上“翻倍”。

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.

问题3)如果在任何时候你看到你正在翻倍,你可以从收集中弹出一些东西并“备份”。然后从那一点尝试再次“前进”。

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.

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

#7

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

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

#8

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

从节点X开始并检查所有子节点(如果未定向,父节点和子节点是等效的)。将这些子节点标记为X的子节点。从任何此类子节点A,将其标记为A,X'的子节点,其中X'标记为2步之外。)。如果你以后点击X并将其标记为X''的子节点,则表示X处于3节点循环中。回溯它的父亲是很容易的(因为,算法不支持这个,所以你找到任何父有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.

注意:如果图形是无向的或具有任何双向边缘,则此算法会变得更复杂,假设您不希望在一个周期内遍历相同的边缘两次。

#9

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.

如果您想要的是在图表中找到所有基本电路,您可以使用自1970年以来在纸上找到的JAMES C. TIERNAN的EC算法。

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

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

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.

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

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

您可能需要学习原始论文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);
?>

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.

然后这是另一个实现,更独立于图形,没有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

?>

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

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

#10

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

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

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

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

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.

来自该顶点的DFS。对于每个节点x,保留两个数字,dfs_index [x]和dfs_lowval [x]。 dfs_index [x]存储访问该节点的时间,而dfs_lowval [x] = min(dfs_low [k])其中k是x的所有子节点,它不是dfs-spanning树中x的直接父节点。

3. All nodes with the same dfs_lowval[x] are in the same strongly connected component.

具有相同dfs_lowval [x]的所有节点都在同一个强连接组件中。

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

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

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.

选择任何起始顶点v,并沿着该顶点的边缘跟踪,直到返回到v。不可能卡在除v之外的任何顶点,因为所有顶点的均匀度确保当轨迹进入另一个顶点时顶点w必须有一个未使用的边缘留下w。以这种方式形成的游览是封闭游览,但可能不会覆盖初始图形的所有顶点和边缘。

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.

只要存在属于当前巡视的顶点v但是相邻边不是巡视的一部分,则从v开始另一条路径,跟随未使用的边,直到返回到v,然后将以这种方式形成的巡回加入到上一次旅行。

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

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

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

#11

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

#12

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)

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

#13

can't you make a little recursive function to traverse the nodes?

你不能做一个小的递归函数来遍历节点吗?

readDiGraph( string pathSoFar, Node x)
{

    if(NoChildren) MasterList.add( pathsofar + Node.name ) ; 

    foreach( child ) 
    {
       readDiGraph( pathsofar + "->" + this.name, child) 
    }
}

if you have a ton of nodes you will run out of stack

如果你有大量的节点,你将耗尽堆栈

#14

Javascript solution using disjoint set linked lists. Can be upgraded to disjoint set forests for faster run times.

使用不相交的集链接列表的Javascript解决方案。可以升级到不相交的集合林以获得更快的运行时间。

var input = '5\nYYNNN\nYYYNN\nNYYNN\nNNNYN\nNNNNY'
console.log(input);
//above solution should be 3 because the components are
//{0,1,2}, because {0,1} and {1,2} therefore {0,1,2}
//{3}
//{4}

//MIT license, authored by Ling Qing Meng

//'4\nYYNN\nYYYN\nNYYN\nNNNY'

//Read Input, preformatting
var reformat = input.split(/\n/);
var N = reformat[0];
var adjMatrix = [];
for (var i = 1; i < reformat.length; i++) {
    adjMatrix.push(reformat[i]);
}

//for (each person x from 1 to N) CREATE-SET(x)
var sets = [];
for (var i = 0; i < N; i++) {
    var s = new LinkedList();
    s.add(i);
    sets.push(s);
}

//populate friend potentials using combinatorics, then filters
var people =  [];
var friends = [];
for (var i = 0; i < N; i++) {
    people.push(i);
}
var potentialFriends = k_combinations(people,2);
for (var i = 0; i < potentialFriends.length; i++){
    if (isFriend(adjMatrix,potentialFriends[i]) === 'Y'){
        friends.push(potentialFriends[i]);
    }
}


//for (each pair of friends (x y) ) if (FIND-SET(x) != FIND-SET(y)) MERGE-SETS(x, y)
for (var i = 0; i < friends.length; i++) {
    var x = friends[i][0];
    var y = friends[i][1];
    if (FindSet(x) != FindSet(y)) {
        sets.push(MergeSet(x,y));
    }
}


for (var i = 0; i < sets.length; i++) {
    //sets[i].traverse();
}
console.log('How many distinct connected components?',sets.length);



//Linked List data structures neccesary for above to work
function Node(){
    this.data = null;
    this.next = null;
}

function LinkedList(){
    this.head = null;
    this.tail = null;
    this.size = 0;

    // Add node to the end
    this.add = function(data){
        var node = new Node();
        node.data = data;
        if (this.head == null){
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = node;
            this.tail = node;
        }
        this.size++;
    };


    this.contains = function(data) {
        if (this.head.data === data) 
            return this;
        var next = this.head.next;
        while (next !== null) {
            if (next.data === data) {
                return this;
            }
            next = next.next;
        }
        return null;
    };

    this.traverse = function() {
        var current = this.head;
        var toPrint = '';
        while (current !== null) {
            //callback.call(this, current); put callback as an argument to top function
            toPrint += current.data.toString() + ' ';
            current = current.next; 
        }
        console.log('list data: ',toPrint);
    }

    this.merge = function(list) {
        var current = this.head;
        var next = current.next;
        while (next !== null) {
            current = next;
            next = next.next;
        }
        current.next = list.head;
        this.size += list.size;
        return this;
    };

    this.reverse = function() {
      if (this.head == null) 
        return;
      if (this.head.next == null) 
        return;

      var currentNode = this.head;
      var nextNode = this.head.next;
      var prevNode = this.head;
      this.head.next = null;
      while (nextNode != null) {
        currentNode = nextNode;
        nextNode = currentNode.next;
        currentNode.next = prevNode;
        prevNode = currentNode;
      }
      this.head = currentNode;
      return this;
    }


}


/**
 * GENERAL HELPER FUNCTIONS
 */

function FindSet(x) {
    for (var i = 0; i < sets.length; i++){
        if (sets[i].contains(x) != null) {
            return sets[i].contains(x);
        }
    }
    return null;
}

function MergeSet(x,y) {
    var listA,listB;
    for (var i = 0; i < sets.length; i++){
        if (sets[i].contains(x) != null) {
            listA = sets[i].contains(x);
            sets.splice(i,1);
        }
    }
    for (var i = 0; i < sets.length; i++) {
        if (sets[i].contains(y) != null) {
            listB = sets[i].contains(y);
            sets.splice(i,1);
        }
    }
    var res = MergeLists(listA,listB);
    return res;

}


function MergeLists(listA, listB) {
    var listC = new LinkedList();
    listA.merge(listB);
    listC = listA;
    return listC;
}

//access matrix by i,j -> returns 'Y' or 'N'
function isFriend(matrix, pair){
    return matrix[pair[0]].charAt(pair[1]);
}

function k_combinations(set, k) {
    var i, j, combs, head, tailcombs;
    if (k > set.length || k <= 0) {
        return [];
    }
    if (k == set.length) {
        return [set];
    }
    if (k == 1) {
        combs = [];
        for (i = 0; i < set.length; i++) {
            combs.push([set[i]]);
        }
        return combs;
    }
    // Assert {1 < k < set.length}
    combs = [];
    for (i = 0; i < set.length - k + 1; i++) {
        head = set.slice(i, i+1);
        tailcombs = k_combinations(set.slice(i + 1), k - 1);
        for (j = 0; j < tailcombs.length; j++) {
            combs.push(head.concat(tailcombs[j]));
        }
    }
    return combs;
}

#15

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.

来自起始节点的DFS,在遍历期间跟踪DFS路径,如果在s的路径中找到来自节点v的边,则记录路径。 (v,s)是DFS树中的后沿,因此表示包含s的循环。

#16

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

关于您关于置换周期的问题,请在此处阅读更多内容: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]);
    }
}

#17

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

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

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

Johnson的算法确实提供了所有独特的简单周期,并且具有良好的时间和空间复杂性。

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.

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

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.

因此,找到MINIMAL循环的最简单方法之一是使用Floyd算法使用邻接矩阵查找所有顶点之间的最小路径。这个算法远没有约翰逊那么理想,但是它非常简单,内部循环非常紧凑,对于较小的图形(<= 50-100个节点),使用它绝对有意义。时间复杂度为O(n ^ 3),空间复杂度为O(n ^ 2),如果使用父跟踪则为O(1),如果不使用则为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
      }
    }
  }

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

最初,该算法在加权边缘图上运行,以找到所有节点对之间的所有最短路径(因此权重参数)。为了使其正常工作,如果节点之间存在有向边缘,则需要提供1,否则提供NO_EDGE。算法执行后,您可以检查主对角线,如果有少于NO_EDGE的值,则该节点参与长度等于该值的循环。同一周期的每个其他节点将具有相同的值(在主对角线上)。

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.

如果顶点之间存在边缘,则父节点矩阵最初应包含边缘单元格中的源顶点索引,否则为-1。函数返回后,对于每个边,您将引用最短路径树中的父节点。然后很容易恢复实际周期。

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