介绍

广度优先搜索算法（英语：Breadth-First Search，缩写为 BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索演算法。简单的说，BFS 是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用 open-closed 表。

演示

• Breadth-First Search【双语 cc 字幕】

• 图的遍历 (广度优先搜索、深度优先搜索）

实现

JavaScript

/**
 * Breadth-first search is an algorithm for traversing a graph.
 *
 * It discovers all nodes reachable from the starting position by exploring all of the neighbor nodes at the present
 * depth prior to moving on to the nodes at the next depth level.
 *
 * (description adapted from https://en.wikipedia.org/wiki/Breadth-first_search)
 * @see https://www.koderdojo.com/blog/breadth-first-search-and-shortest-path-in-csharp-and-net-core
 */
export function breadthFirstSearch (graph, startingNode) {
  // visited keeps track of all nodes visited
  const visited = new Set()

  // queue contains the nodes to be explored in the future
  const queue = [startingNode]

  while (queue.length > 0) {
    // start with the queue's first node
    const node = queue.shift()

    if (!visited.has(node)) {
      // mark the node as visited
      visited.add(node)
      const neighbors = graph[node]

      // put all its neighbors into the queue
      for (let i = 0; i < neighbors.length; i++) {
        queue.push(neighbors[i])
      }
    }
  }

  return visited
}

参考

• Breadth-first search - Wikiwand (opens new window)
• 广度优先搜索 - Wikiwand (opens new window)