If I console.log visited nodes, I get a ton of spare nodes that I don't want.
I just what the nodes necessary to get for start to end node (does not need to be the shortest), But I don't want all the other paths/nodes the algo took before it found the right path
function dfs(start, visited = new Set()) {
console.log(start)
visited.add(start);
const destinations = adjacencyList.get(start);
for (const destination of destinations) {
if (destination === 'BKK') {
console.log(`DFS found Bangkok`)
return;
}
if (!visited.has(destination)) {
dfs(destination, visited);
}
}
}
dfs('PHX')
The idea here is to track if the node destination you visited leads to correct path or not. Hence, you should return after exhausting a particular node whether end node can be visited through this node or not.
function dfs(start, visited = new Set()) {
visited.add(start);
const destinations = adjacencyList.get(start);
var result = false;
for (const destination of destinations) {
if (destination === 'BKK') {
console.log(`DFS found Bangkok`);
console.log(destination);
return true;
}
if (!visited.has(destination)) {
result |= dfs(destination, visited); // you can visit end from this node
}
}
if(result) {
console.log(start);
}
return result;
}
dfs('PHX')
Notice that this will print nodes from start -> finish in reverse order i.e. from finish to start.
To have path from start ..->..finish, you can store in some array(instead of console.log) and reverse that after dfs is complete.