Нахождение всех циклов в ориентированном графе

Как я могу найти (перебрать) ВСЕ циклы в ориентированном графе из / в данный узел?

Например, я хочу что-то вроде этого:

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

но не: B-> C-> B

Я нашел эту страницу в своем поиске, и поскольку циклы не совпадают с сильно связанными компонентами, я продолжил поиск и, наконец, нашел эффективный алгоритм, который перечисляет все (элементарные) циклы ориентированного графа. Это от Дональда Б. Джонсона, и документ можно найти по следующей ссылке:

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

Согласно статье, алгоритм Джонсона является самым быстрым.

Поиск в глубину с возвратом должен работать здесь. Сохраняйте массив логических значений, чтобы отслеживать, посещали ли вы узел ранее. Если у вас заканчиваются новые узлы для перехода (без попадания на узел, которым вы уже были), просто вернитесь назад и попробуйте другую ветвь.

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, то их бесконечное количество. Например, ABA, ABABA и т. Д. Или может быть возможно объединить 2 цикла в 8-подобный цикл и т. Д. И т. Д. Значимый подход заключается в поиске всех так называемых простых циклов - тех, которые не пересекаются, кроме в начальной / конечной точке. Тогда, если вы хотите, вы можете генерировать комбинации простых циклов.

Один из базовых алгоритмов для нахождения всех простых циклов в ориентированном графе состоит в следующем: Выполните обход в глубину всех простых путей (тех, которые не пересекаются) в графе. Каждый раз, когда текущий узел имеет преемника в стеке, обнаруживается простой цикл. Он состоит из элементов в стеке, начиная с идентифицированного преемника и заканчивая вершиной стека. Первичный обход по глубине всех простых путей аналогичен поиску по глубине, но вы не помечаете / записываете посещенные узлы, кроме тех, которые в данный момент находятся в стеке, как точки остановки.

Приведенный выше алгоритм грубой силы ужасно неэффективен, и в дополнение к этому генерирует несколько копий циклов. Это, однако, отправная точка множества практических алгоритмов, которые применяют различные усовершенствования, чтобы улучшить производительность и избежать дублирования цикла. Я был удивлен, узнав некоторое время назад, что эти алгоритмы не всегда доступны в учебниках и в Интернете. Поэтому я провел некоторое исследование и реализовал 4 таких алгоритма и 1 алгоритм для циклов в неориентированных графах в библиотеке Java с открытым исходным кодом здесь: http://code.google.com/p/niographs/ .

Кстати, поскольку я упомянул неориентированные графы: алгоритм для них другой. Создайте остовное дерево, а затем каждое ребро, которое не является частью дерева, образует простой цикл вместе с некоторыми ребрами в дереве. Найденные таким образом циклы образуют так называемую базу циклов. Затем можно найти все простые циклы, комбинируя 2 или более различных базовых цикла. Для получения более подробной информации смотрите, например, это: http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf .

Самый простой выбор, который я нашел для решения этой проблемы, - это использование Python-библиотеки под названием 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']]

Чтобы уточнить:

1. Сильно связанные компоненты найдут все подграфы, в которых есть хотя бы один цикл, а не все возможные циклы в графе. например, если вы возьмете все сильно связанные компоненты и свернете / сгруппируете / объедините каждый из них в один узел (т. е. узел на компонент), вы получите дерево без циклов (на самом деле DAG). Каждый компонент (который является в основном подграфом с по крайней мере одним циклом в нем) может содержать внутри себя еще много возможных циклов, поэтому SCC НЕ найдет все возможные циклы, он найдет все возможные группы, которые имеют по крайней мере один цикл, и если вы группируете их, то на графике не будет циклов.

2. чтобы найти все простые циклы в графе, как уже упоминалось, алгоритм Джонсона является кандидатом.

Однажды мне задали это как вопрос для интервью. Я подозреваю, что это случилось с вами, и вы приходите сюда за помощью. Разбейте проблему на три вопроса, и это станет легче.

1. как вы определяете следующий действующий маршрут
2. Как вы определяете, использовалась ли точка?
3. как избежать повторного перехода через ту же точку

Проблема 1) Используйте шаблон итератора, чтобы обеспечить способ итерации результатов маршрута. Хорошее место для размещения логики для получения следующего маршрута - это, вероятно, «moveNext» вашего итератора. Чтобы найти правильный маршрут, это зависит от вашей структуры данных. Для меня это была таблица sql, полная допустимых маршрутов, поэтому мне пришлось создать запрос, чтобы получить действительные пункты назначения с указанием источника.

Задача 2) Толкайте каждый узел, когда вы находите их в коллекции, по мере их получения, это означает, что вы можете увидеть, очень легко ли вы «удваиваете» точку, опрашивая коллекцию, которую вы строите на лету.

Задача 3) Если в какой-то момент вы видите, что удваиваете назад, вы можете вытолкнуть вещи из коллекции и «сделать резервную копию». Затем с этого момента попробуйте снова «двигаться вперед».

Хак: если вы используете Sql Server 2008, есть некоторые новые «иерархические» вещи, которые вы можете использовать, чтобы быстро решить эту проблему, если вы структурируете свои данные в виде дерева.

Варианты на основе DFS с задними краями действительно найдут циклы, но во многих случаях они НЕ будут минимальными циклами. В общем, DFS дает вам флаг, что цикл существует, но он недостаточно хорош для того, чтобы фактически находить циклы. Например, представьте 5 разных циклов, имеющих два ребра. Нет простого способа идентифицировать циклы, используя только DFS (включая варианты возврата).

Алгоритм Джонсона действительно дает все уникальные простые циклы и имеет хорошую временную и пространственную сложность.

Но если вы хотите просто найти МИНИМАЛЬНЫЕ циклы (это означает, что может быть более одного цикла, проходящего через любую вершину, и мы заинтересованы в поиске минимальных циклов) И ваш граф не очень большой, вы можете попробовать использовать простой метод ниже. Это ОЧЕНЬ просто, но довольно медленно по сравнению с Джонсоном.

Так, один из абсолютно простой способ найти МИНИМАЛЬНЫЕ циклов заключается в использовании алгоритма Флойда , чтобы найти минимальные пути между всеми вершинами , используя матрицу смежности. Этот алгоритм далеко не так оптимален, как алгоритм Джонсона, но он настолько прост, и его внутренний цикл настолько узок, что для небольших графов (<= 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

В случае неориентированного графа недавно опубликованная статья ( Оптимальный список циклов и st-путей в неориентированных графах ) предлагает асимптотически оптимальное решение. Вы можете прочитать его здесь http://arxiv.org/abs/1205.2766 или здесь http://dl.acm.org/citation.cfm?id=2627951 Я знаю, что это не отвечает на ваш вопрос, но так как название в вашем вопросе не указано направление, оно все равно может быть полезным для поиска в Google

Начните с узла X и проверьте все дочерние узлы (родительский и дочерний узлы эквивалентны, если не направлены). Отметьте эти дочерние узлы как дочерние элементы X. От любого такого дочернего узла A отметьте, что его дочерние узлы являются дочерними по отношению к A, X ', где X' помечен как находящийся на расстоянии 2 шагов. Если позже вы нажмете X и отметите его как дочерний элемент X '', это означает, что X находится в цикле из 3 узлов. Возврат к его родителю очень прост (как есть, алгоритм не поддерживает это, поэтому вы можете найти, какой родитель имеет X ').

Примечание. Если график ненаправленный или имеет двунаправленные ребра, этот алгоритм усложняется, если вы не хотите пересекать одно ребро дважды за цикл.

Если вам нужно найти все элементарные схемы на графике, вы можете использовать алгоритм EC Джеймса Тирнана, который был найден в статье с 1970 года.

Очень оригинально алгоритм EC , как мне удалось реализовать в PHP (надеюсь , что нет никаких ошибок приведены ниже). Он также может найти петли, если они есть. Схемы в этой реализации (которые пытаются клонировать оригинал) являются ненулевыми элементами. Ноль здесь означает небытие (ноль, как мы его знаем).

Помимо этого, ниже следует другая реализация, которая дает алгоритму большую независимость, это означает, что узлы могут начинаться откуда угодно, даже с отрицательных чисел, например, -4, -3, -2, и т. Д.

В обоих случаях требуется, чтобы узлы были последовательными.

Возможно, вам придется изучить оригинальную статью, Алгоритм элементарной цепи Джеймса С. Тирнана

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

тогда это другая реализация, более независимая от графа, без перехода и без значений массива, вместо этого она использует ключи массива, путь, график и схемы хранятся в виде ключей массива (используйте значения массива, если хотите, просто измените необходимые линии). Граф примера начинается с -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, но, к сожалению, документация на греческом языке.

Есть два шага (алгоритма), участвующих в поиске всех циклов в DAG.

Первым шагом является использование алгоритма Тарьяна для нахождения набора сильно связанных компонентов.

1. Начните с любой произвольной вершины.
2. DFS из этой вершины. Для каждого узла x сохраните два числа: dfs_index [x] и dfs_lowval [x]. dfs_index [x] сохраняет при посещении этого узла, тогда как dfs_lowval [x] = min (dfs_low [k]), где k - все дочерние элементы x, которые не являются непосредственными родителями x в связующем дереве dfs.
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

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

Я наткнулся на следующий алгоритм, который кажется более эффективным, чем алгоритм Джонсона (по крайней мере, для больших графиков). Однако я не уверен в его производительности по сравнению с алгоритмом Тарьяна.
Кроме того, я проверил только треугольники. Если интересно, см. «Алгоритмы составления списка и подграфа» Норишиге Тиба и Такао Нишизеки ( http://dx.doi.org/10.1137/0214017 )

Решение 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;
}

DFS с начального узла s, отслеживайте путь DFS во время обхода и записывайте путь, если вы найдете ребро от узла v на пути к s. (v, s) является фоном в дереве DFS и, таким образом, указывает цикл, содержащий s.

Относительно вашего вопроса о цикле перестановок , прочитайте больше здесь: 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]);
    }
}

Версия 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();
}