javascript - 如何在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]

其中每条路径的节点从起始节点到第一个遇到的节点，直到最后一个节点。

从邻接表开始，并且不使用递归，这不是收集所有这些路径的最简单方法吗，(所有父路径<的有序父节点/em>) 在我的示例中，从节点 0 开始到节点 6 和 12 结束？

这段代码有什么问题？

Answer 1

您的 rightAdjacent 缺少节点 6 的邻居，这应该是一个空数组。一个简单的解决方案是执行 bfs，但在将节点添加到路径时深度复制访问路径和当前路径。没有邻居时，可以输出/保存当前路径

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

    bfs()