Wie implementiert man die Suche nach allen Pfaden innerhalb eines gerichteten Graphen in JavaScript?

Question

Ich möchte alle verschiedenen Wege ohne Zyklen in folgenden Graphen finden:

Aus diesem Diagramm ich die Adjazenzliste zusammengesetzt, von dem Knoten 0 beginnen und nach rechts gehen (im Bild oben) :

var rightAdjacent = [[1,7],[2],[3,9],[4],[5],[6,10],[8],[2],[5],[11],[12]]; 

Wie ich ein noob in Graphen bin, begann ich von einem kanonischen Algorithmus für BFS, die den billigsten Weg, ich scheint zu bekommen, was ich brauche:

...  
var paths = [] 
queue.push(0); // Starting node 
parents[0] = null; 

while (queue.length > 0) { 
    u = queue.splice(0, 1)[0]; 
    for (i = 0, l= rightAdjacent.length; i < l; i++) { // Explore edge(u, v). 
     v = rightAdjacent[u][i]; 
     if (rightAdjacent[v]) { 
      if(rightAdjacent[v].status === 'unexplored') { 
       rightAdjacent[v].status = 'exploring'; // Node u has been discovered 
       queue.push(v); 
       parents[v] = u; 
      } 
     } else { 
      paths.push(collectPath(parents)); 
     } 
    } 
    rightAdjacent[u].status = 'explored'; 
} 

... aber bei meinem ersten Versuch konnte ich nur die Liste der angeschlossenen Komponenten sammeln, nach denen und bis jetzt nur Müll.

Ich habe auch die Links-Adjazenz-Liste zusammengestellt, nicht wissend, ob dies nützlich sein könnte, um die Suche zu beschleunigen oder den erkannten Pfad zurückzuverfolgen. Irgendwelche Hinweise darauf?

Für die Grafik im Bild erwarten, ich bin folgendes Ergebnis (bitte korrigiert mich wenn iam falsch):

[0,1,2,3,4,5,6], 
[0,1,2,9,5,6], 
[0,1,2,9,5,10,11,12], 
[0,7,8,2,3,4,5,6], 
[0,7,8,2,9,5,10,11,12] 

, wo jeder einzelne Pfad vom Startknoten bestellt die Knoten hat, durch die zuerst angetroffen, bis zum letzten.

Ausgehend von einer Adjazenzliste und ohne Rekursion, wäre es nicht der einfachste Weg, dies alle diese Wege zu sammeln, (die geordneten Elternknoten alles geordnete Pfade) in meinem Beispiel, ausgehend von Knoten 0 und endend bei Knoten 6 und 12?

Was ist in diesem Code falsch?

Answer 1

Ihr rightAdjacent fehlt die Nachbarn von Knoten 6, der ein leeres Array sein sollte. Eine einfache Lösung zu implementieren ist, bfs zu tun, aber den besuchten und den aktuellen Pfad tief zu kopieren, wenn Sie einen Knoten zu Ihrem Pfad hinzufügen. Wenn Sie keine neightbours haben, können Sie die Ausgabe/Speichern den aktuellen Pfad

\t \t var rightAdjacent = [[1,7],[2],[3,9],[4],[5],[6,10],[],[8],[2],[5],[11],[12]]; 
 

 
    var queue = [{visited:{0:true},path:[0]}] // start with node 0 
 

 
    function bfs(){ 
 
     while(queue.length){ 
 
      obj = queue.pop() // get last added path 
 
      node = obj.path[obj.path.length-1] // get last visited node from that path 
 
      visited = obj.visited 
 
      if(node >= rightAdjacent.length || rightAdjacent[node].length == 0){ // we reached a leaf node 
 
       console.log(obj.path) 
 
      }else{ 
 
      for(var i=0;i<rightAdjacent[node].length;i++){ // we need to add the neighbours not visited 
 
       if(!visited[rightAdjacent[node][i]]){ 
 
        visited[rightAdjacent[node][i]] = true 
 
        arr = obj.path.slice(0); 
 
        arr.push(rightAdjacent[node][i]); queue.push({visited:JSON.parse(JSON.stringify(visited)),path:arr}) // deep copy of both 
 
       } 
 
      } 
 
      } 
 
     } \t 
 
    } 
 

 
    bfs()