Menemukan semua siklus dalam grafik yang diarahkan

Bagaimana saya bisa menemukan (beralih di atas) SEMUA siklus dalam grafik berarah dari / ke simpul yang diberikan?

Sebagai contoh, saya ingin sesuatu seperti ini:

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

tetapi tidak: B-> C-> B

Saya menemukan halaman ini dalam pencarian saya dan karena siklus tidak sama dengan komponen yang terhubung kuat, saya terus mencari dan akhirnya, saya menemukan algoritma yang efisien yang mencantumkan semua siklus (dasar) dari grafik yang diarahkan. Itu dari Donald B. Johnson dan makalahnya dapat ditemukan di tautan berikut:

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

Implementasi java dapat ditemukan di:

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

Sebuah Mathematica demonstrasi algoritma Johnson dapat ditemukan disini , implementasi dapat didownload dari kanan ( "Download penulis kode" ).

Catatan: Sebenarnya, ada banyak algoritma untuk masalah ini. Beberapa dari mereka tercantum dalam artikel ini:

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

Menurut artikel itu, algoritma Johnson adalah yang tercepat.

Pencarian pertama dengan backtracking yang dalam harus bekerja di sini. Menyimpan array nilai boolean untuk melacak apakah Anda mengunjungi sebuah node sebelumnya. Jika Anda kehabisan node baru untuk pergi (tanpa memukul node Anda sudah pernah), maka cukup mundur dan coba cabang yang berbeda.

DFS mudah diimplementasikan jika Anda memiliki daftar adjacency untuk mewakili grafik. Misalnya adj [A] = {B, C} menunjukkan bahwa B dan C adalah anak-anak dari A.

Misalnya, pseudo-code di bawah ini. "start" adalah simpul tempat Anda memulai.

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;

Panggil fungsi di atas dengan simpul mulai:

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

Pertama-tama - Anda tidak benar-benar ingin mencoba menemukan semua siklus karena jika ada 1 maka ada jumlah tak terbatas dari mereka. Misalnya ABA, ABABA dll. Atau dimungkinkan untuk bergabung bersama 2 siklus menjadi 8-seperti siklus dll, dll ... Pendekatan yang berarti adalah untuk mencari semua siklus sederhana yang disebut - yang tidak melintasi sendiri kecuali di titik awal / akhir. Kemudian jika Anda mau, Anda bisa menghasilkan kombinasi siklus sederhana.

Salah satu algoritma dasar untuk menemukan semua siklus sederhana dalam grafik terarah adalah ini: Lakukan traversal kedalaman-pertama dari semua jalur sederhana (yang tidak memotong sendiri) dalam grafik. Setiap kali ketika node saat ini memiliki penerus di stack, siklus sederhana ditemukan. Ini terdiri dari elemen-elemen pada stack yang dimulai dengan penerus yang diidentifikasi dan diakhiri dengan bagian atas stack. Traversal pertama yang dalam dari semua jalur sederhana mirip dengan pencarian pertama yang dalam, tetapi Anda tidak menandai / merekam node yang dikunjungi selain yang saat ini ada di stack sebagai titik berhenti.

Algoritma brute force di atas sangat tidak efisien dan selain itu menghasilkan banyak salinan siklus. Namun ini adalah titik awal dari beberapa algoritma praktis yang menerapkan berbagai peningkatan untuk meningkatkan kinerja dan menghindari duplikasi siklus. Saya terkejut mengetahui beberapa waktu lalu bahwa algoritma ini tidak tersedia di buku teks dan di web. Jadi saya melakukan riset dan mengimplementasikan 4 algoritma dan 1 algoritma untuk siklus dalam grafik tidak langsung di perpustakaan Java open source di sini: http://code.google.com/p/niographs/ .

BTW, karena saya sebutkan grafik tidak terarah: Algoritma untuk mereka berbeda. Bangun pohon yang merentang dan kemudian setiap tepi yang bukan bagian dari pohon membentuk siklus sederhana bersama dengan beberapa tepi di pohon. Siklus yang ditemukan dengan cara ini membentuk basis siklus. Semua siklus sederhana kemudian dapat ditemukan dengan menggabungkan 2 atau lebih siklus dasar yang berbeda. Untuk detail lebih lanjut lihat misalnya ini: http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf .

Pilihan paling sederhana yang saya temukan untuk menyelesaikan masalah ini adalah menggunakan python lib bernama networkx.

Itu mengimplementasikan algoritma Johnson yang disebutkan dalam jawaban terbaik dari pertanyaan ini tetapi itu membuat cukup sederhana untuk dieksekusi.

Singkatnya, Anda membutuhkan yang berikut:

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

Jawaban: [['a', 'b', 'd', 'e'], ['a', 'b', 'c']]

Untuk memperjelas:

1. Komponen yang terhubung dengan kuat akan menemukan semua subgraph yang memiliki setidaknya satu siklus di dalamnya, tidak semua siklus yang mungkin dalam grafik. misalnya jika Anda mengambil semua komponen yang sangat terhubung dan runtuh / kelompok / gabungkan masing-masing menjadi satu simpul (yaitu simpul per komponen), Anda akan mendapatkan pohon tanpa siklus (sebenarnya DAG). Setiap komponen (yang pada dasarnya adalah subgraph dengan setidaknya satu siklus di dalamnya) dapat mengandung lebih banyak siklus yang mungkin secara internal, jadi SCC TIDAK akan menemukan semua siklus yang mungkin, itu akan menemukan semua kelompok yang mungkin memiliki setidaknya satu siklus, dan jika Anda mengelompokkan mereka, maka grafik tidak akan memiliki siklus.

2. untuk menemukan semua siklus sederhana dalam grafik, seperti yang disebutkan lainnya, algoritma Johnson adalah kandidat.

Saya pernah diberikan ini sebagai pertanyaan wawancara, saya curiga ini terjadi pada Anda dan Anda datang ke sini untuk meminta bantuan. Pecahkan masalah menjadi tiga pertanyaan dan itu menjadi lebih mudah.

1. bagaimana Anda menentukan rute valid berikutnya
2. bagaimana Anda menentukan apakah suatu titik telah digunakan
3. bagaimana Anda menghindari melewati titik yang sama lagi

Masalah 1) Gunakan pola iterator untuk menyediakan cara mengulangi hasil rute. Tempat yang baik untuk meletakkan logika untuk mendapatkan rute berikutnya mungkin adalah "moveNext" dari iterator Anda. Untuk menemukan rute yang valid, itu tergantung pada struktur data Anda. Bagi saya itu adalah tabel sql yang penuh dengan kemungkinan rute yang valid, jadi saya harus membuat kueri untuk mendapatkan tujuan yang valid dengan sumber.

Masalah 2) Dorong setiap simpul saat Anda menemukan mereka ke dalam koleksi saat Anda mendapatkannya, ini berarti bahwa Anda dapat melihat apakah Anda "menggandakan kembali" pada suatu titik dengan sangat mudah dengan menginterogasi koleksi yang Anda bangun dengan cepat.

Masalah 3) Jika pada suatu saat Anda melihat Anda menggandakan kembali, Anda dapat menghapus hal-hal dari koleksi dan "cadangan". Kemudian sejak saat itu cobalah untuk "bergerak maju" lagi.

Hack: jika Anda menggunakan Sql Server 2008 ada beberapa hal "hierarki" baru yang dapat Anda gunakan untuk menyelesaikan masalah ini dengan cepat jika Anda menyusun data di pohon.

Varian berbasis DFS dengan tepi belakang memang akan menemukan siklus, tetapi dalam banyak kasus BUKAN siklus minimal . Secara umum DFS memberi Anda tanda bahwa ada siklus tetapi tidak cukup baik untuk benar-benar menemukan siklus. Misalnya, bayangkan 5 siklus berbeda yang berbagi dua sisi. Tidak ada cara sederhana untuk mengidentifikasi siklus hanya menggunakan DFS (termasuk varian backtracking).

Algoritma Johnson memang memberikan semua siklus sederhana yang unik dan memiliki kompleksitas ruang dan waktu yang baik.

Tetapi jika Anda hanya ingin menemukan siklus MINIMAL (artinya mungkin ada lebih dari satu siklus melewati titik mana pun dan kami tertarik untuk menemukan yang minimal) DAN grafik Anda tidak terlalu besar, Anda dapat mencoba menggunakan metode sederhana di bawah ini. Ini SANGAT sederhana tetapi agak lambat dibandingkan dengan Johnson.

Jadi, salah satu benar-benar cara termudah untuk menemukan siklus MINIMAL adalah dengan menggunakan algoritma Floyd untuk menemukan jalan minimal antara semua simpul menggunakan matriks ketetanggaan. Algoritma ini tidak seoptimal Johnson, tetapi sangat sederhana dan loop dalamnya sangat ketat sehingga untuk grafik yang lebih kecil (<= 50-100 node) sangat masuk akal untuk menggunakannya. Kompleksitas waktu adalah O (n ^ 3), kompleksitas ruang O (n ^ 2) jika Anda menggunakan pelacakan induk dan O (1) jika tidak. Pertama-tama mari kita cari jawaban untuk pertanyaan jika ada siklus. Algoritma ini sangat sederhana. Di bawah ini cuplikan di 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
      }
    }
  }

Awalnya algoritma ini beroperasi pada grafik tepi tertimbang untuk menemukan semua jalur terpendek di antara semua pasangan node (karenanya argumen bobot). Agar dapat bekerja dengan benar, Anda harus memberikan 1 jika ada tepi yang diarahkan antara node atau NO_EDGE sebaliknya. Setelah algoritma dijalankan, Anda dapat memeriksa diagonal utama, jika ada nilai kurang dari NO_EDGE dari node ini berpartisipasi dalam siklus panjang yang sama dengan nilai. Setiap simpul lain dari siklus yang sama akan memiliki nilai yang sama (pada diagonal utama).

Untuk merekonstruksi siklus itu sendiri kita perlu menggunakan versi algoritma yang sedikit dimodifikasi dengan pelacakan induk.

  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
      }
    }
  }

Matriks induk pada awalnya harus mengandung indeks titik sumber dalam sel tepi jika ada tepi antara simpul dan -1. Setelah fungsi kembali, untuk setiap tepi Anda akan memiliki referensi ke simpul induk di pohon jalur terpendek. Dan kemudian mudah untuk memulihkan siklus yang sebenarnya.

Secara keseluruhan, kami memiliki program berikut untuk menemukan semua siklus minimal

  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
  }

dan metode utama kecil hanya untuk menguji hasilnya

  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")
  }

dan hasilnya

The following minimal cycle found:
012
Total: 1 cycle found

Dalam kasus grafik tidak terarah, sebuah makalah yang baru-baru ini diterbitkan ( daftar optimal siklus dan jalur di grafik tidak berarah ) menawarkan solusi optimal asimtotik. Anda dapat membacanya di sini http://arxiv.org/abs/1205.2766 atau di sini http://dl.acm.org/citation.cfm?id=2627951 Saya tahu itu tidak menjawab pertanyaan Anda, tetapi karena judul pertanyaan Anda tidak menyebutkan arah, mungkin masih berguna untuk pencarian Google

Mulai dari simpul X dan periksa semua simpul anak (simpul induk dan simpul sama jika tidak diarahkan). Tandai simpul anak tersebut sebagai anak-anak X. Dari simpul anak A seperti itu, tandai anak-anak menjadi anak-anak A, X ', di mana X' ditandai sebagai 2 langkah jauhnya.). Jika Anda kemudian menekan X dan menandainya sebagai anak X '', itu berarti X dalam siklus 3 simpul. Mengulangi ke induknya itu mudah (apa adanya, algoritme tidak memiliki dukungan untuk ini sehingga Anda akan menemukan orangtua mana pun yang memiliki X ').

Catatan: Jika grafik tidak diarahkan atau memiliki tepi dua arah, algoritma ini menjadi lebih rumit, dengan asumsi Anda tidak ingin melintasi tepi yang sama dua kali untuk satu siklus.

Jika yang Anda inginkan adalah menemukan semua rangkaian elementer dalam grafik, Anda dapat menggunakan algoritma EC, oleh JAMES C. TIERNAN, yang ditemukan di kertas sejak 1970.

The sangat asli algoritma EC karena saya berhasil menerapkannya di php (harapan tidak ada kesalahan ditampilkan di bawah). Itu dapat menemukan loop juga jika ada. Sirkuit dalam implementasi ini (yang mencoba mengkloning yang asli) adalah elemen bukan nol. Nol di sini berarti tidak ada (nol seperti yang kita tahu).

Terlepas dari itu di bawah ini mengikuti implementasi lain yang memberikan algoritma lebih mandiri, ini berarti node dapat mulai dari mana saja bahkan dari angka negatif, misalnya -4, -3, -2, .. dll.

Dalam kedua kasus itu diperlukan bahwa node adalah berurutan.

Anda mungkin perlu mempelajari makalah asli, 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);
?>

maka ini adalah implementasi lain, lebih independen dari grafik, tanpa nilai goto dan tanpa array, alih-alih menggunakan kunci array, path, grafik dan sirkuit disimpan sebagai kunci array (gunakan nilai array jika Anda suka, cukup ubah yang diperlukan baris). Contoh grafik mulai dari -4 untuk menunjukkan independensinya.

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

?>

Saya telah menganalisis dan mendokumentasikan EC tetapi sayangnya dokumentasinya dalam bahasa Yunani.

Ada dua langkah (algoritma) yang terlibat dalam menemukan semua siklus dalam DAG.

Langkah pertama adalah menggunakan algoritma Tarjan untuk menemukan set komponen yang sangat terhubung.

1. Mulai dari sembarang titik.
2. DFS dari titik itu. Untuk setiap simpul x, pertahankan dua angka, dfs_index [x] dan dfs_lowval [x]. dfs_index [x] menyimpan ketika simpul itu dikunjungi, sementara dfs_lowval [x] = min (dfs_low [k]) di mana k adalah semua anak-anak x yang bukan merupakan induk langsung dari x dalam pohon span-dfs.
3. Semua node dengan dfs_lowval yang sama [x] berada di komponen yang sangat terhubung.

Langkah kedua adalah menemukan siklus (jalur) di dalam komponen yang terhubung. Saran saya adalah menggunakan versi modifikasi dari algoritma Hierholzer.

Idenya adalah:

1. Pilih titik awal mana pun v, dan ikuti jejak tepian dari titik itu sampai Anda kembali ke v. Tidak mungkin terjebak di titik mana pun selain v, karena derajat genap semua simpul memastikan bahwa, ketika jejak memasuki yang lain simpul w harus ada tepi yang tidak digunakan meninggalkan w. Tur yang dibentuk dengan cara ini adalah tur tertutup, tetapi mungkin tidak mencakup semua simpul dan tepi grafik awal.
2. Selama ada titik v yang menjadi bagian dari tur saat ini tetapi memiliki tepi yang berdekatan bukan bagian dari tur, mulai jejak lain dari v, ikuti tepi yang tidak digunakan sampai Anda kembali ke v, dan bergabung dengan tur yang dibentuk dengan cara ini ke tur sebelumnya.

Berikut ini tautan ke implementasi Java dengan test case:

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

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

Saya tersandung pada algoritma berikut yang tampaknya lebih efisien daripada algoritma Johnson (setidaknya untuk grafik yang lebih besar). Namun saya tidak yakin tentang kinerjanya dibandingkan dengan algoritma Tarjan.
Selain itu, saya hanya memeriksanya untuk segitiga sejauh ini. Jika tertarik, silakan lihat "Algoritma Pencatatan Subgraph dan Subgraph" oleh Norishige Chiba dan Takao Nishizeki ( http://dx.doi.org/10.1137/0214017 )

Solusi Javascript menggunakan daftar tertaut yang disjoint set. Dapat ditingkatkan untuk memisahkan pengaturan hutan untuk waktu lari yang lebih cepat.

var input = '5\nYYNNN\nYYYNN\nNYYNN\nNNNYN\nNNNNY'
console.log(input);
//above solution should be 3 because the components are
//{0,1,2}, because {0,1} and {1,2} therefore {0,1,2}
//{3}
//{4}

//MIT license, authored by Ling Qing Meng

//'4\nYYNN\nYYYN\nNYYN\nNNNY'

//Read Input, preformatting
var reformat = input.split(/\n/);
var N = reformat[0];
var adjMatrix = [];
for (var i = 1; i < reformat.length; i++) {
    adjMatrix.push(reformat[i]);
}

//for (each person x from 1 to N) CREATE-SET(x)
var sets = [];
for (var i = 0; i < N; i++) {
    var s = new LinkedList();
    s.add(i);
    sets.push(s);
}

//populate friend potentials using combinatorics, then filters
var people =  [];
var friends = [];
for (var i = 0; i < N; i++) {
    people.push(i);
}
var potentialFriends = k_combinations(people,2);
for (var i = 0; i < potentialFriends.length; i++){
    if (isFriend(adjMatrix,potentialFriends[i]) === 'Y'){
        friends.push(potentialFriends[i]);
    }
}


//for (each pair of friends (x y) ) if (FIND-SET(x) != FIND-SET(y)) MERGE-SETS(x, y)
for (var i = 0; i < friends.length; i++) {
    var x = friends[i][0];
    var y = friends[i][1];
    if (FindSet(x) != FindSet(y)) {
        sets.push(MergeSet(x,y));
    }
}


for (var i = 0; i < sets.length; i++) {
    //sets[i].traverse();
}
console.log('How many distinct connected components?',sets.length);



//Linked List data structures neccesary for above to work
function Node(){
    this.data = null;
    this.next = null;
}

function LinkedList(){
    this.head = null;
    this.tail = null;
    this.size = 0;

    // Add node to the end
    this.add = function(data){
        var node = new Node();
        node.data = data;
        if (this.head == null){
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = node;
            this.tail = node;
        }
        this.size++;
    };


    this.contains = function(data) {
        if (this.head.data === data) 
            return this;
        var next = this.head.next;
        while (next !== null) {
            if (next.data === data) {
                return this;
            }
            next = next.next;
        }
        return null;
    };

    this.traverse = function() {
        var current = this.head;
        var toPrint = '';
        while (current !== null) {
            //callback.call(this, current); put callback as an argument to top function
            toPrint += current.data.toString() + ' ';
            current = current.next; 
        }
        console.log('list data: ',toPrint);
    }

    this.merge = function(list) {
        var current = this.head;
        var next = current.next;
        while (next !== null) {
            current = next;
            next = next.next;
        }
        current.next = list.head;
        this.size += list.size;
        return this;
    };

    this.reverse = function() {
      if (this.head == null) 
        return;
      if (this.head.next == null) 
        return;

      var currentNode = this.head;
      var nextNode = this.head.next;
      var prevNode = this.head;
      this.head.next = null;
      while (nextNode != null) {
        currentNode = nextNode;
        nextNode = currentNode.next;
        currentNode.next = prevNode;
        prevNode = currentNode;
      }
      this.head = currentNode;
      return this;
    }


}


/**
 * GENERAL HELPER FUNCTIONS
 */

function FindSet(x) {
    for (var i = 0; i < sets.length; i++){
        if (sets[i].contains(x) != null) {
            return sets[i].contains(x);
        }
    }
    return null;
}

function MergeSet(x,y) {
    var listA,listB;
    for (var i = 0; i < sets.length; i++){
        if (sets[i].contains(x) != null) {
            listA = sets[i].contains(x);
            sets.splice(i,1);
        }
    }
    for (var i = 0; i < sets.length; i++) {
        if (sets[i].contains(y) != null) {
            listB = sets[i].contains(y);
            sets.splice(i,1);
        }
    }
    var res = MergeLists(listA,listB);
    return res;

}


function MergeLists(listA, listB) {
    var listC = new LinkedList();
    listA.merge(listB);
    listC = listA;
    return listC;
}

//access matrix by i,j -> returns 'Y' or 'N'
function isFriend(matrix, pair){
    return matrix[pair[0]].charAt(pair[1]);
}

function k_combinations(set, k) {
    var i, j, combs, head, tailcombs;
    if (k > set.length || k <= 0) {
        return [];
    }
    if (k == set.length) {
        return [set];
    }
    if (k == 1) {
        combs = [];
        for (i = 0; i < set.length; i++) {
            combs.push([set[i]]);
        }
        return combs;
    }
    // Assert {1 < k < set.length}
    combs = [];
    for (i = 0; i < set.length - k + 1; i++) {
        head = set.slice(i, i+1);
        tailcombs = k_combinations(set.slice(i + 1), k - 1);
        for (j = 0; j < tailcombs.length; j++) {
            combs.push(head.concat(tailcombs[j]));
        }
    }
    return combs;
}

DFS dari mulai simpul s, melacak jalur DFS selama traversal, dan merekam jalur jika Anda menemukan tepi dari simpul v di jalur ke s. (v, s) adalah back-edge di pohon DFS dan dengan demikian menunjukkan siklus yang mengandung s.

Mengenai pertanyaan Anda tentang Siklus Permutasi , baca lebih lanjut di sini: https://www.codechef.com/problems/PCYCLE

Anda dapat mencoba kode ini (masukkan ukuran dan nomor digit):

# 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]);
    }
}

Versi DFS c ++ untuk kode semu di jawaban lantai dua:

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();
}