如何使用图节点 'BKKK' 获取 console.log('found it!') 进行广度优先搜索遍历

Question

相信你做得很好，我正在使用下面的图表遍历使用 Node.js 找到名为 BKKK

的机场的所有 edges or routes

但不知何故代码没有显示 console.log('found it!') 在代码中我传递了 BreadthFirst 搜索函数并将起始节点作为 'PHX'

谁能告诉我下面的代码出了什么问题，为什么编译代码时不显示 console.log('found it!')？

            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');

非常感谢您的帮助

此致

卡罗琳

Answer 1

这是适合您的更新代码：

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');

问题：

第 49 行你有一个拼写错误
因为你添加到目标队列是在一个 if 块内，它检查目标是否是你正在寻找的目标，因为拼写错误，它永远不会到达，即使它被修复也不会解决如果机场不是直接相连的问题
您没有将所有可能的目的地添加到队列中

建议：

为了让这段代码更实用一些，可以简化为：

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');

如何使用图节点 'BKKK' 获取 console.log('found it!') 进行广度优先搜索遍历

How to get console.log('found it!') for Breadth First Search Traversal Using Graph Node 'BKKK'

javascript

breadth-first-search

node.js

javascript-objects

graph-algorithm