deblocker - 11 months ago 74

Javascript Question

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):

`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:

`...`

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

What is wrong in this piece of code?

Answer

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

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

Source (Stackoverflow)