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

Question

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

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

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

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

Answer 1

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

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

Answer 2

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

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

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

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

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

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

Answer 3

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

DFS легко реализовать, если у вас есть список смежности для представления графика. Например, adj [A] = {B, C} указывает, что B и C являются дочерними элементами A.

Например, псевдокод. «Начало» - это тот узел, с которого вы начинаете.

dfs(adj,node,visited): 
    if (visited[node]): 
    if (node == start): 
     "found a path" 
    return; 
    visited[node]=YES; 
    for child in adj[node]: 
    dfs(adj,child,visited) 
    visited[node]=NO; 

Вызова выше функции с начальным узлом:

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

Answer 4

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

Answer 5

вы не можете сделать немного рекурсивную функцию для обхода узлов?

readDiGraph(string pathSoFar, Node x) 
{ 

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

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

, если у вас есть тонна узлов вы будете бежать из стека

Answer 6

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

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

Реализация Java можно найти в:

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

Mathematica демонстрация Алгоритм Джонсона можно найти here, реализация может быть загружена с правой стороны ("Download author code").

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

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

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

Answer 7

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

Answer 8

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

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

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

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

Вы, возможно, потребуется изучить оригинальную бумагу, James C. Tiernan Elementary Circuit Algorithm

<?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, но, к сожалению, документация находится на греческом языке.

Answer 9

Прежде всего - вы действительно не пытаетесь найти буквально все циклы, потому что если есть 1, то существует бесконечное число таких. Например, ABA, ABABA и т. Д. Или может быть возможно объединить 2 цикла в 8-подобный цикл и т. Д. И т. Д. ... Значимый подход - искать все так называемые простые циклы - те, которые не пересекаются, кроме в начальной/конечной точке. Затем, если хотите, вы можете создавать комбинации простых циклов.

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

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

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

Answer 10

Существует два этапа (алгоритмы), связанные с поиском всех циклов в 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-spanning.
3. Все узлы с одинаковым dfs_lowval [x] находятся в одном и том же сильно соединенном компоненте.

Второй шаг - найти циклы (пути) в соединенных компонентах.Мое предложение - использовать модифицированную версию алгоритма Иерхолзера.

Идея такова:

1. Выберите любую начальную вершину V, и следовать след ребер от этой вершины до тех пор, пока не вернетесь к V Это невозможно застрять в любой вершине, кроме V,. потому что четная степень всех вершин гарантирует, что, когда тропа входит в другую вершину w, должно быть неиспользованное ребро, выходящее из w. Тур, сформированный таким образом, является закрытым туром, но может не охватывать все вершины и ребра начального графа.
2. Пока существует вершина v, относящаяся к текущему туру, но имеющая смежные ребра, не входящие в тур, запустите другой след из v, после неиспользуемых краев, пока вы не вернетесь в v, и не присоединитесь к турне, сформированному в этом путь к предыдущему туру.

Вот ссылка на реализацию Java с тестом:

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

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

Для уточнения:

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

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

Answer 15

Что касается вашего вопроса о перестановочного цикла, читайте здесь: https://www.codechef.com/problems/PCYCLE

Вы можете попробовать этот код (введите размер и цифры номера):

# include<cstdio> 
using namespace std; 

int main() 
{ 
    int n; 
    scanf("%d",&n); 

    int num[1000]; 
    int visited[1000]={0}; 
    int vindex[2000]; 
    for(int i=1;i<=n;i++) 
     scanf("%d",&num[i]); 

    int t_visited=0; 
    int cycles=0; 
    int start=0, index; 

    while(t_visited < n) 
    { 
     for(int i=1;i<=n;i++) 
     { 
      if(visited[i]==0) 
      { 
       vindex[start]=i; 
       visited[i]=1; 
       t_visited++; 
       index=start; 
       break; 
      } 
     } 
     while(true) 
     { 
      index++; 
      vindex[index]=num[vindex[index-1]]; 

      if(vindex[index]==vindex[start]) 
       break; 
      visited[vindex[index]]=1; 
      t_visited++; 
     } 
     vindex[++index]=0; 
     start=index+1; 
     cycles++; 
    } 

    printf("%d\n",cycles,vindex[0]); 

    for(int i=0;i<(n+2*cycles);i++) 
    { 
     if(vindex[i]==0) 
      printf("\n"); 
     else 
      printf("%d ",vindex[i]); 
    } 
} 

Answer 16

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

Ответ: [[ 'а', 'B', 'D', 'е'], [ 'а', 'б', «с»]]

Answer 17

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

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

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

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