BFS应用-寻找最短路径

const getShortestPaths = (graph, startVertex) => {
    const vertices = graph.getVertices();
    const adjList = graph.getAdjList();
    
    const distances = {};
    const pre = {};
    vertices.forEach((vertex) => { distances[vertex] = 0; })
    
    const queue = [startVertex];
    const visited = {};
    visited[startVertex] = 1;
    
    while (queue.length > 0) {
        const e = queue.shift();
        for (const neighbor of adjList.get(e)) {
            if (visited[neighbor] !== 1) {
                visited[neighbor] = 1; //visited
                distances[neighbor] = distances[e] + 1;
                pre[neighbor] = e;
                queue.push(neighbor);
            }
        }
    }

    return {
        distances,
        pre
    };
}

const findShortestWay = (shortestPaths, startVertex, endVertex) => {
    let s = startVertex;
    for (let v = endVertex; v !== startVertex; v = shortestPaths.pre[v]) {
        s += ` - ${v}`;
    }
    return s;
}

(() => {
    const graph = new AdjGraph();
    initGraph(graph);
    console.log(graph.toString());
    
    const start = "A", end = "B"; //寻找A到B的最短路径
    const shortestPaths = getShortestPaths(graph, start);
    console.log(shortestPaths.distances);
    console.log(shortestPaths.pre);
    const shortestWay = findShortestWay(shortestPaths, start, end);
    console.log(shortestWay);
})()