如何在JavaScript中的有向圖內實現對所有路徑的搜索？

Question

我想找到在以下圖表無環的所有不同的路徑：

從該曲線圖中，我組成的鄰接表，從節點0開始和（上圖中）要右：

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

，因爲我在圖一小白，我從一個典型算法BFS，這在我看來，最便宜的方式來獲得我所需要的開始：

...  
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'; 
} 

...但在我的第一次嘗試中，我只能收集連接組件的列表，在此之後，直到現在，只有垃圾。

我也編寫了左鄰接表，不知道這可能對加速搜索或回溯發現的路徑有用。有關這個的任何線索？

對於畫面中的圖形，我期待下面的結果（請糾正我，如果我'錯）：

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

其中每個單獨的路徑已經從起始節點有序的節點，通過第一次遇到，直到最後。

從鄰接表開始，並且不使用遞歸，不會是這個收集所有這個路徑（在下令父節點的所有父路徑的）在我的例子中，最簡單的方法，開始從節點0到節點6和12結束？

這段代碼有什麼問題？

Answer 1

你的rightAdjacent缺少節點6的鄰居，應該是一個空的數組。一個簡單的解決方案是執行bfs，但在向路徑添加節點時深度複製訪問路徑和當前路徑。當你有沒有neightbours，您可以輸出/保存當前的路徑

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