学习JavaScript数据结构与算法 — 广度优先搜索算法
广度优先搜索（BFS）
上一次已经提到，图的遍历一般有两种算法，即广度优先和深度优先。其中广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层。换句话说，就是先宽后深地访问顶点，如图1。
图1
从顶点v开始的广度优先搜索的步骤如下：
- 创建一个队列Q。
- 将v标注为被发现的（灰色） ，并将v入队列Q。
如果Q非空，则运行以下步骤：
- 将u从队列Q中取出
- 将u标注为被发现的（灰色）
- 将u所有未被访问过的邻节点（白色）加入队列
- 将u标注为已被探索的（黑色）
我们用三种状态来反映顶点的状态：
- 白色：表示该顶点还没有被访问。
- 灰色：表示该顶点被访问过，但并未被探索过。
- 黑色：表示该顶点被访问过且被完全探索过。
因此在算法开始执行时，需要将所有顶点置为白色；如下代码所示（本文的所有代码都是在图中实现的Graph类中添加的），其中vertices保存着图所有顶点的名字。
function Graph() {
var vertices = [];
var adjList = new Dictionary();
// 图类的其他代码省略...
var initializeColor = function(){
var color = [];
for (var i=0; i<vertices.length; i++){
color[vertices[i]] = 'white';
}
return color;
};
}广度优先搜索算法的核心代码如下，其中队列Queue的实现参考基于JavaScript的数据结构 — 队列的实现
this.bfs = function(v, callback){
var color = initializeColor(), // 将所有顶点初始化为白色
queue = new Queue(); // 实例化队列
queue.enqueue(v); // 将起始顶点v加入队列
while (!queue.isEmpty()){ // 一直循环处理队列，直到队列为空
var u = queue.dequeue(), // 移除队列顶部的元素，并取得该顶点
neighbors = adjList.get(u); // 获取该顶点的相邻顶点
color[u] = 'grey'; // 将该顶点置为灰色，表明该顶点被访问过，但并未被探索过
for (var i=0; i<neighbors.length; i++){ // 循环处理该顶点的相邻顶点
var w = neighbors[i];
if (color[w] === 'white'){ // 如果该顶点没有被访问过
color[w] = 'grey'; // 将该顶点置为灰
queue.enqueue(w); // 将该顶点加入队列
}
}
color[u] = 'black'; // 该顶点访问已经被完全访问，将其置为黑
callback && callback(u); // 用回调函数处理该节点（如果有）
}
};使用BFS寻找最短路径
由于广度优先算法是一层层往下遍历的，即先访问与起始顶点距离为1的点，再访问距离为2的点，以此类推。因此，给定一个图G和源顶点v， 要找出每一个顶点u与v之间的最短距离（以边的数量计算），可以在上述代码的基础上做一定修改（修改的位置用空行隔开）：
// 获取路径信息
this.pathData = function(v){
var color = initializeColor(),
queue = new Queue(),
d = new Array(vertices.length).fill(0), // 用于保存起始顶点v到任意顶点u的距离
pred = new Array(vertices.length).fill(null); // 用于保存v到u的路径上u的上一级顶点（前溯点）
queue.enqueue(v);
while (!queue.isEmpty()){
var u = queue.dequeue(),
neighbors = adjList.get(u);
color[u] = 'grey';
for (i=0; i<neighbors.length; i++){
var w = neighbors[i];
if (color[w] === 'white'){
color[w] = 'grey';
d[w] = d[u] + 1; // w到u的距离差是1
pred[w] = u; // w的上一级顶点是u
queue.enqueue(w);
}
}
color[u] = 'black';
}
return { // 返回保存的数据
distances: d,
predecessors: pred
};
};
// 格式化输出路径信息
this.printPathData = function (pathData) {
var fromVertex = vertices[0]; // 获取起始点
for (var i=1; i<vertices.length; i++){
var toVertex = vertices[i], // 要到达的顶点
path = []; // 用于保存路径
// 从目标顶点一直回溯到起始顶点
for (var v=toVertex; v!== fromVertex; v= pathData.predecessors[v]) {
path.push(v); // 顶点添加进路径
}
path.push(fromVertex); // 将起始顶点添加进路径
var s = path.pop();
while (path.length > 0){
s += ' - ' + path.pop(); // 从路径数组倒序输出顶点
}
console.log(s);
}
}通过执行Graph.printPathData(Graph.pathData())即可输出起始顶点到每一个顶点的最短路径。
其它最短路径算法
对于加权图的最短路径，广度优先算法可能并不合适。比如，Dijkstra’s算法可以解决单源最短路径问题。Bellman–Ford算法解决了边权值为负的单源最短路径问题。A*搜索算法解决了求仅一对顶点间的最短路径问题，它用经验法则来加速搜索过程。Floyd–Warshall算法解决了求所有顶点对间的最短路径这一问题。