Confíe en que lo está haciendo muy bien, estoy usando el gráfico transversal a continuación usando Node.js para encontrar todos los edges or routes para el aeropuerto llamado BKKK
Pero de alguna manera el código no BreadthFirst la console.log('found it!') 'PHX'
¿Puede alguien decirme qué está mal en el siguiente código? ¿Por qué no se muestra console.log('found it!') al compilar el código?
const airports = 'PHX BKK OKC JFK LAX MEX EZE HEL LOS LAP LIM'.split(' '); const routes = [ ['PHX','LAX'], ['PHX','JFK'], ['JFK','OKC'], ['JFK','HEL'], ['JFK','LOS'], ['MEX','LAX'], ['MEX','BKK'], ['MEX','LIM'], ['MEX','EZE'], ['LIM','BKK'], ]; //The Graph const adjacencyList = new Map(); //add-node function addnode(airport){ adjacencyList.set(airport, []); } //Add edge,undirected function addEdge(origin,destination){ adjacencyList.get(origin).push(destination); adjacencyList.get(destination).push(origin); } //Create the Graph airports.forEach(addnode); routes.forEach(route => addEdge(...route)); console.log(adjacencyList); //BFS Breadth First Search function bfs(start){ const visited = new Set(); const queue = [start] while (queue.length > 0) { const airport = queue.shift(); const destinations = adjacencyList.get(airport); for(const destination of destinations){ if(destination === 'BKKK'){ console.log('found it!'); if(!visited.has(destination)){ visited.add(destination); queue.push(destination); } } } } } bfs('PHX');Tu ayuda es altamente apreciada
Saludos
Carolina
Aquí está el código actualizado que funcionará para usted:
const airports = 'PHX BKK OKC JFK LAX MEX EZE HEL LOS LAP LIM'.split(' '); const routes = [ ['PHX', 'LAX'], ['PHX', 'JFK'], ['JFK', 'OKC'], ['JFK', 'HEL'], ['JFK', 'LOS'], ['MEX', 'LAX'], ['MEX', 'BKK'], ['MEX', 'LIM'], ['MEX', 'EZE'], ['LIM', 'BKK'], ]; //The Graph const adjacencyList = new Map(); //add-node function addnode(airport) { adjacencyList.set(airport, []); } //Add edge,undirected function addEdge(origin, destination) { adjacencyList.get(origin).push(destination); adjacencyList.get(destination).push(origin); } //Create the Graph airports.forEach(addnode); routes.forEach(route => addEdge(...route)); console.log(adjacencyList); //BFS Breadth First Search function bfs(start) { const visited = new Set(); const queue = [start]; while (queue.length > 0) { const airport = queue.shift(); const destinations = adjacencyList.get(airport); for (const destination of destinations) { if (destination === 'BKK') { console.log('found it!'); break; } if (!visited.has(destination)) { visited.add(destination); queue.push(...adjacencyList.get(destination)); } } } } bfs('PHX');problemas:
Sugerencias:
Para hacer este código un poco más funcional, se puede simplificar a esto:
const routes = [ ['PHX', 'LAX'], ['PHX', 'JFK'], ['JFK', 'OKC'], ['JFK', 'HEL'], ['JFK', 'LOS'], ['MEX', 'LAX'], ['MEX', 'BKK'], ['MEX', 'LIM'], ['MEX', 'EZE'], ['LIM', 'BKK'], ]; const makeGraph = routes => { return routes.reduce((list, [origin, destination]) => { console.log(origin, destination); if (!list.get(origin)) { list.set(origin, []); } if (!list.get(destination)) { list.set(destination, []); } list.get(origin).push(destination); list.get(destination).push(origin); return list; }, new Map()); }; //find if there is a route between two airports const findRoute = (graph, origin, destination) => { const queue = [origin]; const visited = new Set(); while (queue.length) { const airport = queue.shift(); if (airport === destination) { console.log('found it!'); break; } if (!visited.has(airport)) { visited.add(airport); queue.push(...graph.get(airport)); } } return false; }; const graph = makeGraph(routes); findRoute(graph, 'PHX', 'BKK');