Si console.log visité los nodos, obtengo una tonelada de nodos de repuesto que no quiero.
Solo tengo los nodos necesarios para obtener el nodo de inicio a fin (no es necesario que sea el más corto), pero no quiero todas las otras rutas/nodos que tomó el algoritmo antes de encontrar la ruta correcta.
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')La idea aquí es rastrear si el destination del nodo que visitó conduce a la ruta correcta o no. Por lo tanto, debe regresar después de agotar un nodo en particular si el nodo final se puede visitar a través de este nodo o no.
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') Tenga en cuenta que esto imprimirá los nodos desde el inicio -> final en orden inverso, es decir, desde el final hasta el inicio.
Para tener una ruta desde start ..->..finish , puede almacenar en alguna matriz (en lugar de console.log) y revertir eso después de que dfs esté completo.