如何在JavaScript中实现有向图内所有路径的搜索？

I would like to find all distinct paths without cycles in following graph:

我想在下面的图中找到所有不带循环的不同路径:

From this graph, i composed the adjacency list, starting from node 0 and going to the right (in the picture above):

从这张图中,我组成了邻接列表,从节点0开始,向右移动(如上图所示):

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

As i am a noob in graphs, i started from a canonical algorithm for BFS, which seems to me the cheapest way to get what i need:

由于我是图表中的菜鸟,我从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'; 
}

... but in my first attempt i was able to collect only the list of the connected components, after which and until now, only garbage.

...但是在我的第一次尝试中,我只能收集连接组件的列表,在此之后,直到现在,只有垃圾。

I have also composed the left-adjacency list, not knowing if this could be useful to speed up the search or to back-trace the discovered path. Any clue about this?

我还编写了左邻接列表,不知道这对于加速搜索或回溯已发现的路径是否有用。关于这个的任何线索?

For the graph in the picture, i'm expecting following result (please correct me if i'am wrong):

对于图中的图表,我期待以下结果(如果我错了,请纠正我):

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

where each single path has the nodes ordered from the starting node, through the first encountered, until the last.

其中每个单一路径都有从起始节点开始排序的节点,通过第一个遇到的节点,直到最后一个节点。

Starting from an adjacency list, and without using recursion, wouldn't it be this the simplest way to collect all this paths, (the ordered parent nodes of all the parent paths) in my example, starting from node 0 and ending at nodes 6 and 12?

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

What is wrong in this piece of code?

这段代码有什么问题?

1 个解决方案

#1

Your rightAdjacent is missing the neighbours of node 6, which should be an empty array. An easy solution to implement is to do bfs but deep copy the visited and current path when you add a node to your path. When you have no neightbours, you can output/save the current path

你的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()