介绍

BFS 能用于寻找图中的最短路径，除非：

• 不存在循环
• 所有的边都有相同的权重或没有权重。

为了找到最短的路径，你所要做的就是从源头开始，进行广度优先的搜索，当你找到目标节点时就停止。你唯一需要做的是有一个数组 previous [n]，它将存储每个被访问节点的前一个节点。源的前一个节点可以是空的。要打印路径，只需从源点开始循环浏览 previous [] 数组，直到到达目标节点。在类似条件下，DFS 也可以用来寻找图中的最短路径。

但是，如果图形更复杂，包含加权边和循环，那么我们就需要一个更复杂的 BFS 版本，即 Dijkstra 的算法。

如果我们想在一个无向的、无权重的图中找到最短路径（undirected, unweighted graph），那么 BFS 就是要使用的算法。BFS 的主张是，在遍历过程中第一次发现一个节点时，该节点与源头的距离即为最短路径。在普遍的图中，广度优先搜索没有办法知道某一个节点的发现是否会给我们带来通往该节点的最短路径。于是，BFS（或 DFS）在加权图中找到最短路径的唯一可能方式是搜索整个图并不断记录从源点到目的顶点的最小距离。这种解决方案在复杂的场景下不可行的，除非给定一些限制条件。

演示

视频讲述广度优先搜索相关知识，还涉及最短路径、floodFill 等实际应用问题。

实现

JavaScript

/**
 * Breadth-first approach can be applied to determine the shortest path between two nodes in an equi-weighted graph.
 *
 * It searches the target node among all neighbors of the starting node, then the process is repeated on the level of
 * the neighbors of the neighbors and so on.
 *
 * @see 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 breadthFirstShortestPath (graph, startNode, targetNode) {
  // check if startNode & targetNode are identical
  if (startNode === targetNode) {
    return [startNode]
  }

  // visited keeps track of all nodes visited
  const visited = new Set()

  // queue contains the paths to be explored in the future
  const initialPath = [startNode]
  const queue = [initialPath]

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

    // explore this node if it hasn't been visited yet
    if (!visited.has(node)) {
      // mark the node as visited
      visited.add(node)

      const neighbors = graph[node]

      // create a new path in the queue for each neighbor
      for (let i = 0; i < neighbors.length; i++) {
        const newPath = path.concat([neighbors[i]])

        // the first path to contain the target node is the shortest path
        if (neighbors[i] === targetNode) {
          return newPath
        }

        // queue the new path
        queue.push(newPath)
      }
    }
  }

  // the target node was not reachable
  return []
}

扩展

• 广度优先搜索算法在 Unity 网格地图中寻找最短路径

参考

• java - How does a Breadth-First Search work when looking for Shortest Path? - Stack Overflow (opens new window)
• Finding Shortest Paths using Breadth First Search (opens new window)