deblocker - 3 months ago 24
Javascript Question

# How to implement the search for all paths inside a directed graph in 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):

``````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).
rightAdjacent[v].status = 'exploring'; // Node u has been discovered
queue.push(v);
parents[v] = u;
}
} else {
paths.push(collectPath(parents));
}
}
}
``````

... 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?

What is wrong in this piece of code?

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

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{