BFS广度优先遍历

基于之前的邻接表AdjGraph实现
- startVertex需要在入队前就单独处理好
- 出队的作用只是寻找邻居neighbor，因为对该元素的处理在入队前就已完成
  - visited一定要在入队前就标记，否则可能造成后面已入队元素重复入队

const breadthFirstSearch = (graph, startVertex) => {
    const vertices = graph.getVertices();
    const adjList = graph.getAdjList();

    const res = [startVertex];
    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
                res.push(neighbor); //operation
                queue.push(neighbor);
            }
        }
    }

    return res;
}

(() => {
    const graph = new AdjGraph();
    initGraph(graph);
    console.log(graph.toString());
    console.log(breadthFirstSearch(graph, "A"));
    console.log(breadthFirstSearch(graph, "D"));
})()

Keyboard shortcuts

BFS广度优先遍历