如何在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()