Нахождение всех циклов в ориентированном графе
Как я могу найти (перебрать) ВСЕ циклы в ориентированном графе из / в данный узел?
Например, я хочу что-то вроде этого:
A->B->A
A->B->C->A
но не: B->C->B
19 ответов
Я нашел эту страницу в своем поиске, и поскольку циклы не совпадают с сильно связанными компонентами, я продолжил поиск и, наконец, нашел эффективный алгоритм, который перечисляет все (элементарные) циклы ориентированного графа. Это от Дональда Б. Джонсона, и документ можно найти по следующей ссылке:
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)
Самый простой выбор, который я нашел, чтобы решить эту проблему, - это использование python lib 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, то их бесконечное количество. Например, 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.
Варианты на основе 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
Чтобы уточнить:
Сильно связанные компоненты найдут все подграфы, в которых есть хотя бы один цикл, а не все возможные циклы в графе. например, если вы возьмете все сильно связанные компоненты и свернете / сгруппируете / объедините каждый из них в один узел (то есть узел на компонент), вы получите дерево без циклов (на самом деле DAG). Каждый компонент (который в основном является подграфом с хотя бы одним циклом в нем) может содержать внутри себя еще много возможных циклов, поэтому SCC НЕ найдет все возможные циклы, он найдет все возможные группы, имеющие хотя бы один цикл, и если вы группируете их, то на графике не будет циклов.
чтобы найти все простые циклы в графе, как уже упоминалось, алгоритм Джонсона является кандидатом.
Однажды мне задали это как вопрос для интервью. Я подозреваю, что это случилось с вами, и вы приходите сюда за помощью. Разбейте проблему на три вопроса, и это станет легче.
- как вы определяете следующий действительный маршрут
- Как вы определяете, использовалась ли точка?
- как избежать повторного перехода через ту же точку
Проблема 1) Используйте шаблон итератора, чтобы обеспечить способ итерации результатов маршрута. Хорошее место для размещения логики для получения следующего маршрута - это, вероятно, "moveNext" вашего итератора. Чтобы найти правильный маршрут, это зависит от вашей структуры данных. Для меня это была таблица sql, полная допустимых маршрутов, поэтому мне пришлось составить запрос, чтобы получить действительные пункты назначения с указанием источника.
Задача 2) Толкайте каждый узел, когда вы находите их в коллекции, по мере их получения, это означает, что вы можете увидеть, очень легко ли вы "удваиваете" заданную точку, опрашивая коллекцию, которую вы строите на лету.
Задача 3) Если в какой-то момент вы видите, что удваиваете назад, вы можете вытолкнуть вещи из коллекции и "сделать резервную копию". Затем с этого момента попробуйте снова "двигаться вперед".
Хак: если вы используете Sql Server 2008, есть некоторые новые "иерархические" вещи, которые вы можете использовать, чтобы быстро решить эту проблему, если вы структурируете свои данные в виде дерева.
В случае неориентированного графа недавно опубликованная статья (Оптимальный список циклов и 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').
Примечание. Если график ненаправленный или имеет двунаправленные ребра, этот алгоритм усложняется, если вы не хотите пересекать одно ребро дважды за цикл.
Есть два шага (алгоритма), участвующих в поиске всех циклов в DAG.
Первым шагом является использование алгоритма Тарьяна, чтобы найти множество сильно связанных компонентов.
- Начните с любой произвольной вершины.
- DFS из этой вершины. Для каждого узла x сохраните два числа: dfs_index[x] и dfs_lowval[x]. dfs_index[x] сохраняет, когда этот узел посещается, а dfs_lowval[x] = min(dfs_low[k]), где k - все дочерние элементы x, которые не являются непосредственными родителями x в связующем дереве dfs.
- Все узлы с одинаковым 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
Если вам нужно найти все элементарные схемы на графике, вы можете использовать алгоритм 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, но, к сожалению, документация на греческом языке.
Вы не можете сделать небольшую рекурсивную функцию для обхода узлов?
readDiGraph( string pathSoFar, Node x)
{
if(NoChildren) MasterList.add( pathsofar + Node.name ) ;
foreach( child )
{
readDiGraph( pathsofar + "->" + this.name, child)
}
}
если у вас есть тонна узлов, вы выйдете из стека
DFS с начального узла s, отслеживайте путь DFS во время обхода и записывайте путь, если вы найдете ребро от узла v на пути к s. (v,s) является фоном в дереве DFS и, таким образом, указывает цикл, содержащий s.
Решение 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;
}
Я наткнулся на следующий алгоритм, который кажется более эффективным, чем алгоритм Джонсона (по крайней мере, для больших графиков). Однако я не уверен в его производительности по сравнению с алгоритмом Тарьяна.
Кроме того, я только проверил это на треугольники. Если интересно, см. "Алгоритмы составления списка и подграфа" Норишиге Тиба и Такао Нишизеки ( http://dx.doi.org/10.1137/0214017)
Версия 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();
}
Относительно вашего вопроса о цикле перестановок, прочитайте больше здесь: 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]);
}
}