Поиск всех циклов в ориентированном графе
Как я могу найти (перебрать) ВСЕ циклы в ориентированном графе от/до заданного node?
Например, я хочу что-то вроде этого:
A->B->A
A->B->C->A
но не: В- > С- > В
Ответы
Ответ 1
Я нашел эту страницу в своем поиске и так как циклы не такие же, как сильно связанные компоненты, я продолжал искать и, наконец, нашел эффективный алгоритм, который перечисляет все (элементарные) циклы ориентированного графа. Это от Дональда Б. Джонсона, и документ можно найти по следующей ссылке:
http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF
Реализацию java можно найти в:
http://normalisiert.de/code/java/elementaryCycles.zip
В математической демонстрации алгоритма Джонсона можно найти здесь, реализация может быть загружена с правой стороны ( "Загрузить код автора" ).
Примечание. На самом деле для этой проблемы существует множество алгоритмов. Некоторые из них перечислены в этой статье:
http://dx.doi.org/10.1137/0205007
Согласно статье, алгоритм Джонсона является самым быстрым.
Ответ 2
Глубокий первый поиск с обратным следом должен работать здесь.
Храните массив логических значений, чтобы отслеживать, посещали ли вы ранее node. Если у вас заканчиваются новые узлы, чтобы перейти (без удара node, которые вы уже были), тогда просто отступите назад и попробуйте другую ветку.
DFS легко реализовать, если у вас есть список смежности для представления графика. Например, adj [A] = {B, C} указывает, что B и C являются дочерними элементами A.
Например, псевдокод ниже. "start" - это node, с которого вы начинаете.
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;
Вызвать вышеуказанную функцию с помощью запуска node:
visited = {}
dfs(adj,start,visited)
Ответ 3
Прежде всего - вы действительно не хотите пытаться найти буквально все циклы, потому что если есть 1, то их будет бесконечное число. Например, ABA, ABABA и т.д. Или может быть возможно объединить 2 цикла в 8-подобный цикл и т.д. И т.д.... Значимый подход - искать все так называемые простые циклы - те, которые не пересекаются, кроме в начальной/конечной точке. Затем, если хотите, вы можете создавать комбинации простых циклов.
Один из базовых алгоритмов для поиска всех простых циклов в ориентированном графе таков: выполните первый шаг по пересечению всех простых путей (тех, которые не пересекаются) на графике. Каждый раз, когда текущий node имеет преемника в стеке, обнаруживается простой цикл. Он состоит из элементов в стеке, начиная с идентифицированного преемника и заканчивая вершиной стека. Глубина первого обхода всех простых путей аналогична первому поиску глубины, но вы не отмечаете/не записываете посещенные узлы, отличные от тех, которые в настоящее время находятся в стеке, как точки остановки.
Алгоритм грубой силы выше ужасно неэффективен и в дополнение к этому генерирует несколько копий циклов. Однако это является отправной точкой множества практических алгоритмов, которые применяют различные улучшения для повышения производительности и предотвращения дублирования циклов. Я с удивлением обнаружил, что эти алгоритмы недоступны в учебниках и в Интернете. Поэтому я провел некоторое исследование и реализовал 4 таких алгоритма и 1 алгоритм для циклов в неориентированных графах в библиотеке Java с открытым исходным кодом: http://code.google.com/p/niographs/.
Кстати, поскольку я упоминал неориентированные графики: алгоритм для них различен. Постройте остовное дерево, а затем каждое ребро, которое не является частью дерева, образует простой цикл вместе с некоторыми ребрами в дереве. Циклы, найденные таким образом, образуют так называемую базу циклов. Все простые циклы можно найти, объединив 2 или более различных базовых цикла. Более подробно см., Например, это: http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf.
Ответ 4
Самый простой выбор, который я нашел для решения этой проблемы, - это использование библиотеки 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']]
![введите описание изображения здесь]()
Ответ 5
Чтобы уточнить:
-
Сильно соединенные компоненты найдут все подграфы, которые содержат по крайней мере один цикл, а не все возможные циклы на графике. например если вы берете все сильно связанные компоненты и сворачиваете/группируете/объединяете каждый из них в один node (т.е. node на компонент), вы получите дерево без циклов (фактически DAG). Каждый компонент (который в основном является подграфом с по меньшей мере одним циклом в нем) может содержать гораздо больше возможных циклов внутри, поэтому SCC НЕ найдет все возможные циклы, он найдет все возможные группы, которые имеют по крайней мере один цикл, и если вы группируете их, то график не будет иметь циклов.
-
чтобы найти все простые циклы в графе, как упоминалось выше, алгоритм Джонсона является кандидатом.
Ответ 6
Мне дали это как вопрос интервью один раз, я подозреваю, что это случилось с вами, и вы приезжаете сюда за помощью. Разделите проблему на три вопроса, и вам станет легче.
- как вы определяете следующий действительный
маршрут
- как вы определяете, имеет ли точка
был использован
- Как вы избегаете пересечения
то же самое снова
Проблема 1)
Используйте шаблон итератора, чтобы обеспечить способ повторения результатов маршрута. Хорошим местом для логики, чтобы получить следующий маршрут, вероятно, является "moveNext" вашего итератора. Чтобы найти правильный маршрут, это зависит от вашей структуры данных. Для меня это была таблица sql, полная допустимых возможностей маршрута, поэтому мне пришлось создать запрос, чтобы получить действительные адресаты с учетом источника.
Проблема 2)
Нажимайте каждый node, когда вы находите их в коллекции по мере их получения, это означает, что вы можете увидеть, достаточно ли вы "удвоитесь назад" над точкой, опросив коллекцию, которую вы строите на лету.
Задача 3)
Если в какой-то момент вы видите, что вы удваиваете назад, вы можете вытащить вещи из коллекции и "создать резервную копию". Затем с этого момента попробуйте снова "двигаться вперед".
Взлом: если вы используете Sql Server 2008, есть некоторые новые "иерархические" вещи, которые вы можете использовать для быстрого решения этой проблемы, если вы структурируете свои данные в дереве.
Ответ 7
Существует два этапа (алгоритмы), связанные с поиском всех циклов в DAG.
Первым шагом является использование алгоритма Тарьяна для нахождения набора сильно связанных компонентов.
- Начните с любой произвольной вершины.
- DFS из этой вершины. Для каждого node x держите два числа, dfs_index [x] и dfs_lowval [x].
dfs_index [x] сохраняет, когда этот node посещается, а dfs_lowval [x] = min (dfs_low [k]), где
k - все дочерние элементы x, которые не являются прямым родителем x в дереве dfs-spanning.
- Все узлы с одинаковым dfs_lowval [x] находятся в одном и том же сильно подключенном компоненте.
Второй шаг - найти циклы (пути) в подключенных компонентах. Мое предложение - использовать модифицированную версию алгоритма Иерхолзера.
Идея такова:
- Выберите любую начальную вершину v и следуйте по следам ребер из этой вершины, пока не вернетесь к v.
Невозможно застревать в любой вершине, отличной от v, потому что четная степень всех вершин гарантирует, что, когда след входит в другую вершину w, должно быть неиспользованное ребро, выходящее из w. Тур, сформированный таким образом, является закрытым туром, но может не охватывать все вершины и ребра начального графа.
- Пока существует вершина v, относящаяся к текущему туру, но имеющая смежные ребра, не входящие в тур, запустите другой след из v, после неиспользованных краев, пока вы не вернетесь в v, и не присоединитесь к турне, сформированному в этом путь к предыдущему туру.
Вот ссылка на реализацию Java с тестовым примером:
http://stones333.blogspot.com/2013/12/find-cycles-in-directed-graph-dag.html
Ответ 8
В случае неориентированного графика, опубликованная недавно публикация (Оптимальный список циклов и st-путей в неориентированных графах) предлагает асимптотически оптимальное решение. Вы можете прочитать его здесь http://arxiv.org/abs/1205.2766 или здесь http://dl.acm.org/citation.cfm?id=2627951
Я знаю, что он не отвечает на ваш вопрос, но поскольку название вашего вопроса не указывает направление, оно может быть полезно для поиска Google
Ответ 9
Начните с node X и проверьте все дочерние узлы (родительский и дочерний узлы эквивалентны, если они ненаправлены). Отметьте эти дочерние узлы как дети X. Из любого такого дочернего node A отметьте его дочерними элементами дочерних элементов A, X ', где X' отмечен как 2 шага.). Если вы позже нажмете X и отметьте его как дочерний элемент X '', это означает, что X находится в цикле 3 node. Откат к нему родительский легко (как есть, алгоритм не поддерживает этого, так что вы обнаружите, какой из родителей имеет X).
Примечание. Если граф неориентирован или имеет какие-либо двунаправленные ребра, этот алгоритм усложняется, если вы не хотите проходить один и тот же ребро дважды для цикла.
Ответ 10
Если вы хотите найти все элементарные схемы на графике, вы можете использовать алгоритм EC, написанный JAMES C. TIERNAN, найденный на бумаге с 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);
?>
то это другая реализация, более независимая от графика, без goto и без значений массива, вместо этого она использует ключи массива, путь, график и схемы хранятся в виде ключей массива (используйте значения массива, если хотите, просто изменить требуемые строки). Примерный график начинается с -4, чтобы показать его независимость.
<?php
$G = array(
-4=>array(-4=>true,-3=>true,-2=>true),
-3=>array(-4=>true,-3=>true,-2=>true),
-2=>array(-4=>true,-3=>true,-2=>true)
);
$C = array();
EC($G,$C);
echo "<pre>";
print_r($C);
function EC($G, &$C){
$CNST_not_closed = false; // this flag indicates no closure
$CNST_closed = true; // this flag indicates closure
// define the state where there is no closures for some node
$tmp_first_node = key($G); // first node = first key
$tmp_last_node = $tmp_first_node-1+count($G); // last node = last key
$CNST_closure_reset = array();
for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){
$CNST_closure_reset[$k] = $CNST_not_closed;
}
// define the state where there is no closure for all nodes
for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){
$H[$k] = $CNST_closure_reset; // Key in the closure arrays represent nodes
}
unset($tmp_first_node);
unset($tmp_last_node);
# Start algorithm
foreach($G as $init_node => $children){#[Jump to initial node set]
#[Initial Node Set]
$P = array(); // declare at starup, remove the old $init_node from path on loop
$P[$init_node]=true; // the first key in P is always the new initial node
$k=$init_node; // update the current node
// On loop H[old_init_node] is not cleared cause is never checked again
do{#Path 1,3,7,4 jump here to extend father 7
do{#Path from 1,3,8,5 became 2,4,8,5,6 jump here to extend child 6
$new_expansion = false;
foreach( $G[$k] as $child => $foo ){#Consider each child of 7 or 6
if( $child>$init_node and isset($P[$child])===false and $H[$k][$child]===$CNST_not_closed ){
$P[$child]=true; // add this child to the path
$k = $child; // update the current node
$new_expansion=true;// set the flag for expanding the child of k
break(1); // we are done, one child at a time
} } }while(($new_expansion===true));// Do while a new child has been added to the path
# If the first node is child of the last we have a circuit
if( isset($G[$k][$init_node])===true ){
$C[] = $P; // Leaving this out of closure will catch loops to
}
# Closure
if($k>$init_node){ //if k>init_node then alwaya count(P)>1, so proceed to closure
$new_expansion=true; // $new_expansion is never true, set true to expand father of k
unset($P[$k]); // remove k from path
end($P); $k_father = key($P); // get father of k
$H[$k_father][$k]=$CNST_closed; // mark k as closed
$H[$k] = $CNST_closure_reset; // reset k closure
$k = $k_father; // update k
} } while($new_expansion===true);//if we don't wnter the if block m has the old k$k_father_old = $k;
// Advance Initial Vertex Context
}//foreach initial
}//function
?>
Я проанализировал и задокументировал EC, но, к сожалению, документация находится на греческом языке.
Ответ 11
http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf
Ответ 12
Вы не можете сделать небольшую рекурсивную функцию для перемещения узлов?
readDiGraph( string pathSoFar, Node x)
{
if(NoChildren) MasterList.add( pathsofar + Node.name ) ;
foreach( child )
{
readDiGraph( pathsofar + "->" + this.name, child)
}
}
если у вас тонна узлов, у вас закончится стек
Ответ 13
Я наткнулся на следующий алгоритм, который кажется более эффективным, чем алгоритм Джонсона (по крайней мере для больших графов). Однако я не уверен в его производительности по сравнению с алгоритмом Тарьяна.
Кроме того, я только проверил это для треугольников. Если вы заинтересованы, см. "Алгоритмы лингвистики и подграфа" Норришиджа Чиба и Такао Нисизики (http://dx.doi.org/10.1137/0214017)
Ответ 14
Решение 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 с начала node s, отслеживать путь DFS во время обхода и записывать путь, если вы найдете ребро из node v в пути к s. (v, s) является обратным краем в дереве DFS и, таким образом, указывает цикл, содержащий s.
Ответ 16
Что касается вашего вопроса о перестановочном цикле, читайте здесь:
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]);
}
}
Ответ 17
Варианты на основе DFS с задними краями действительно найдут циклы, но во многих случаях это НЕ будет минимальным циклом. В общем, DFS дает вам флаг, что есть цикл, но он недостаточно хорош, чтобы фактически находить циклы. Например, представьте себе 5 разных циклов, разделяющих два края. Нет простого способа идентифицировать циклы, используя только DFS (включая варианты обратного отслеживания).
Джонсон-алгоритм действительно дает все уникальные простые циклы и имеет хорошую временную и пространственную сложность.
Но если вы хотите просто найти MINIMAL-циклы (это означает, что может быть больше одного цикла, проходящего через любую вершину, и мы заинтересованы в поиске минимальных). И ваш график не очень большой, вы можете попытаться использовать простой ниже.
Это ОЧЕНЬ просто, но довольно медленно по сравнению с Джонсоном.
Итак, один из абсолютно самый простой способ найти MINIMAL-циклы - использовать алгоритм Флойда для поиска минимальных путей между всеми вершинами с использованием матрицы смежности.
Этот алгоритм нигде не близок как оптимальный, как у Джонсона, но он настолько прост, и его внутренний цикл настолько туго, что для меньших графов (< = 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, чем этот node участвует в цикле длины, равном значению. Каждый другой node того же цикла будет иметь одинаковое значение (по главной диагонали).
Чтобы восстановить сам цикл, нам нужно использовать слегка модифицированную версию алгоритма с родительским отслеживанием.
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.
После возврата функции для каждого ребра у вас будет ссылка на родительский node в кратчайшем пути.
И тогда легко восстановить фактические циклы.
В целом у нас есть следующая программа, чтобы найти все минимальные циклы
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
