查找有向圖中的所有周期

Question

如何從給定節點中查找（遍歷）有向圖中的所有周期？

例如，我想是這樣的：

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

但不是： B-> C->乙

Answer 1

開始在節點X和檢查所有子節點（父和子節點如果是無向的，則是等同的）。將這些子節點標記爲X的子節點。從任何這樣的子節點A中，將它標記爲A，X'的子節點，其中X'標記爲2步遠）。如果以後按X並將其標記爲X的子項，則表示X處於3節點循環中。回溯到它的父母很容易（因爲算法不支持這個，所以你會發現父母有X'）。

注意：如果圖是無向的或有任何雙向邊，假設您不想在一個週期內兩次遍歷相同的邊，則此算法會變得更加複雜。

Answer 2

我曾經作爲一個面試問題給過這個，我懷疑這件事發生在你身上，你會來這裏尋求幫助。將問題分解爲三個問題，並且變得更容易。

1. 你如何確定下一個有效 路線
2. 如何確定一個點是否已經 被用來
3. 你如何避免跨過 相同點再次

問題1） 使用迭代器模式提供迭代路由結果的方法。將邏輯放到下一條路線的好地方可能就是迭代器的「moveNext」。要找到有效的路由，它取決於您的數據結構。對我來說，這是一個充滿有效路由可能性的sql表，所以我必須構建一個查詢來獲取給定源的有效目標。

問題2） 當您找到它們時，將每個節點推送到一個集合中，這意味着您可以通過詢問正在構建的集合非常容易地看到您是否「倍增」飛。

問題3） 如果在任何時候你看到你翻倍了，你可以從集合中彈出東西並「備份」。然後從那一點開始嘗試再次「前進」。如果您使用的是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

一個數學示範約翰遜的算法可以找到here，實現可以從右邊下載（"Download author code"）。

注意：實際上，這個問題有很多算法。他們中的一些列在這篇文章中：

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

文章認爲，約翰遜的算法是最快的國家之一。

Answer 7

我偶然發現下面的算法似乎比約翰遜的算法更有效率（至少對於更大的圖）。然而，與Tarjan算法相比，我不確定它的性能。
此外，我目前只檢查了三角形。如果感興趣，請參閱千葉千葉和高尾西下紀的「Arboricity and Subgraph Listing Algorithms」（http://dx.doi.org/10.1137/0214017）

Answer 8

如果你想要的是在圖中找到所有的基本電路，你可以使用EC算法，由JAMES C. TIERNAN ，自1970年以來在紙上發現。

非常原始 EC算法，因爲我設法在PHP中實現它（希望沒有錯誤，如下所示）。如果有的話，它也可以找到循環。這個實現中的電路（試圖克隆原始電路）是非零元素。零這裏代表不存在（null，因爲我們知道它）。

除此之外下面如下的其他實施方式，使該算法更加獨立，這意味着這些節點可以從任何地方甚至從負數，例如-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); 
?> 

那麼這是其他實施，更加獨立的圖形，沒有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，但不幸的是文檔是用希臘文寫成的。

Answer 9

首先 - 你並不是真的想嘗試從字面上找到所有的循環，因爲如果有1個，那麼就有無數個循環。例如ABA，ABABA等。或者可能將2個週期連接在一起，形成一個類似8的週期等等。有意義的方法是尋找所謂的簡單週期 - 那些除了自身之外不交叉的週期在開始/結束點。然後，如果您希望可以生成簡單循環的組合。

在有向圖中查找所有簡單循環的基準算法之一是：在圖中對所有簡單路徑（那些不自己交叉的）進行深度優先遍歷。每當當前節點在棧上有一個後繼時，就會發現一個簡單的循環。它由堆棧上的元素組成，以識別的後繼者開始，以堆棧頂部結束。所有簡單路徑的深度第一次遍歷與深度優先搜索類似，但不標記/記錄當前在堆棧中的已訪問節點作爲停止點。

上面的蠻力算法是非常低效的，除此之外還產生了多個週期副本。然而，它是多種實用算法的起點，它們應用各種增強功能以​​提高性能並避免週期複製。我很驚訝地發現，這些算法在教科書和網絡上都不是很容易找到。所以我做了一些研究，並在開源Java庫中實現了4個這樣的算法和1個無向圖中的循環算法：http://code.google.com/p/niographs/。

順便說一句，因爲我提到了無向圖：這些算法是不同的。構建一棵生成樹，然後每個不屬於樹的邊都與樹中的一些邊形成一個簡單的循環。這種循環形成了一個所謂的循環基礎。然後可以通過組合2個或更多個不同的基本循環來找到所有簡單循環。有關更多詳情，請參閱這個：http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf。

Answer 10

在DAG中查找所有周期涉及兩個步驟（算法）。

第一步是使用Tarjan算法找到強連通組件組。

1. 從任意的頂點開始。
2. 從該頂點的DFS。對於每個節點x，保留兩個數字dfs_index [x]和dfs_lowval [x]。 dfs_index [x]在訪問該節點時存儲，而dfs_lowval [x] = min（dfs_low [k]）其中 k是x的所有子項，它不是dfs生成樹中x的直接父項。
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

Answer 11

在無向圖，最近發表了一篇文章的情況下（週期和ST-的最佳上市無向圖中的路徑）提供了漸近最優解。你可以閱讀在這裏http://arxiv.org/abs/1205.2766或這裏http://dl.acm.org/citation.cfm?id=2627951 我知道它不回答你的問題，而是因爲你的問題的標題沒有提及方向，它可能仍然是有用的谷歌搜索

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從起始節點S，跟蹤DFS路徑遍歷期間，如果你發現從節點U的路徑秒的邊緣記錄的路徑。 （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

的我發現解決這個問題最簡單的選擇是使用名爲networkx的Python庫。

它實現了這個問題的最佳答案中提到的約翰遜算法，但它使得執行起來非常簡單。

總之需要進行如下：

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

Answer 17

背部邊緣基於DFS-變種會發現週期確實，但在許多情況下，它不會被最小週期。一般來說，DFS給你的標誌是有一個週期，但它不足以真正找到週期。例如，想象共享兩條邊的5個不同的週期。使用DFS（包括回溯變體）沒有簡單的方法來識別週期。

約翰遜的算法確實給出了所有獨特的簡單循環，並具有良好的時間和空間複雜性。

但是，如果您只想查找MINIMAL循環（意思是可能有多個循環經過任何頂點並且我們有興趣尋找最小的循環）並且您的圖形不是很大，您可以嘗試使用下面簡單的方法。 與約翰遜相比，它非常簡單但相當緩慢。

因此，找到MINIMAL週期的最簡單方法之一是使用Floyd算法來找到所有頂點之間使用鄰接矩陣的最小路徑。 這個算法遠不如約翰遜的算法最優，但它非常簡單，其內部循環非常緊密，以至於對於更小的圖（< = 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 
     } 
    } 
    } 

本來這算法加權邊圖形操作以找到節點的所有對（因此權重參數）之間的所有最短路徑。爲了正常工作，如果節點之間存在有向邊或NO_EDGE，則需要提供1。 算法執行後，您可以檢查主對角線，如果有值小於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