前言
有一个树形无向图，它描述了国、省、市、区之间的层级关系，此时我们想找图中的某一个结点，它位于图中的第几层，此时你应该怎么做？
本文将以图文的形式，详细讲解广度优先搜索，并用JavaScript将其实现，完成上面所描述的问题，欢迎各位感兴趣的开发者阅读本文。
概念
广度优先搜索是一种对图进行搜索的算法。
假设我们一开始位于某个结点（即起点），此时并不知道图的整体结构，而我们的目的是从起点开始顺着边搜索，直到到达指定顶点（即终点）。在此过程中每走到一个顶点，就会判断一次它是否为终点。广度优先搜索会优先从离起点近的顶点开始搜索。
本文涉及到了图与队列，对此不了解的开发者，可以阅读我的另外两篇文章：图的认识 &栈与队列
图解示例
如图所示，A为起点，G为终点。一开始我们在起点A上，此时并不知道G在哪里。
- 将可以从A知道的三个顶点B、C、D设为下一步的候补顶点
- 从候补顶点中选出一个顶点。优先选择最早称为候补的那个顶点，如果有多个顶点同时称为候补，那么可以随意选择其中一个。
- 此处B、C、D同时称为候补，所以我们随机选择了最左边的顶点B。
- 将起点移动至顶点B，将B变为红色，同时将已经搜索过的顶点变为橙色。
- 将可以从B直达的两个顶点E和F设为候补顶点
- 此时最早成为候补顶点的是C和D，我们选择了左边的顶点C。
- 移动顶点到C上
- 将可以从C直达的顶点H设为候补顶点
- 重复上述操作，直到到达终点，或者所有的顶点都被遍历为止。
- 此时，我们的顶点到达了E，从A到E它的搜索顺序为：
A -> B A -> C A -> D B -> E
- 完成了A到I的搜索，现在顶点在J处
- 到达终点G，搜索结束
# 从顶点A到终点G，搜索顺序如下 A -> B A -> C A -> D B -> E B -> F C -> H D -> I D -> J E -> K F H -> G
❝广度优先搜索的特征为从起点开始，由近及远进行广泛的搜索。因此，目标顶点离起点越近，搜索结束得就越快。
❞
用JS实现广度优先搜索
正如图解示例所述，广度优先搜索会从一个顶点出发，广泛搜索它的子结点，将其子结点放进候选顶点中，判断当前顶点是否为终点，如果不是终点则按顺序取出候选顶点中的数据执行上述操作，直至找到终点为止。
操作候选结点时，我们是按顺序取出候选结点，符合了数据结构：「队列的特性」（先进先出）
因此，我们需要先实现一个队列用于存储候选结点
- 实现一个队列，用于存放候选结点
/** * 实现一个基础队列 * @constructor */ const Queue = function () { // 使用数组初始化队列 let items = []; // 向队列插入元素 this.enqueue = function (elem) { items.push(elem); } // 从队头删除元素 this.dequeue = function () { return items.shift(); } // 查看队头元素 this.front = function () { return items[0]; } // 判断队列是否为空 this.isEmpty = function () { return items.length ===0; } // 查看队列长度 this.size = function () { return items.length; } // 查看队列中的元素 this.print = function () { return items.toString(); } }
- 声明一个函数，参数为：要查找的树形图，要查找的结点
- 实例化一个队列，声明顶点到目标节点的深度变量并初始化为0
- 将树加入队列中
- 遍历队列，直至队列为空或者找到目标结点
- 每遍历一次，顶点到目标结点的深度就+1
- 遍历队列中的元素
- 如果当前队列中的元素等于目标元素，则返回当前深度
- 如果不是，则判断是否有下一层，将下一层的预选结点添加进队列
- 删除遍历过的结点
❝我们将上述思路转换为代码
❞
/** * 广度优先搜索 * @param tree 要查找的树形图 * @param target 要查找的结点 * @returns {number} 返回目标结点在树中的深度 */ const breadthFirstSearch = function (tree,target) { // 实例化一个队列 let queue = new Queue(); // 根节点到目标结点的深度 let step = 0; // 入队 queue.enqueue(tree); // 遍历队列，直至队列为空，或者找到目标结点 while (!queue.isEmpty()){ step += 1; let len = queue.size(); for (let i = 0; i < len; i++){ // 获取队首元素 let teamLeader = queue.front(); // 如果是目标元素则返回当前深度 if(target === teamLeader.value) return step; // 如果不是，将下一层结点添加进队列 if(teamLeader.children && teamLeader.children.length){ teamLeader.children.map(item=>{ queue.enqueue(item); }); } // 删除遍历过的结点 queue.dequeue(); } } }
❝接下来，我们用一个例子来测试下我们编写的广度优先搜索函数
❞
如下图所示，是一个描述了国、省、市、区的对应关系的无向图，我们的问题是：从图中找到天河区在第几层。
- 准备数据
// 我们用json来描述上面的无向图 const dataTree = { name:"国家", value:"中国", children:[ { name:"省份", value:"广东", children: [ { name:"城市", value:"广州", children:[ { name:"行政区", value:"天河区", }, /// 其他部分省略 //// ] }, { name:"城市", value: "深圳", children: [ { name:"行政区", value: "福田区" }, /// 其他部分省略 //// ] } ] }, { name:"省份", value:"陕西", children: [ { name:"城市", value: "西安", children: [ /// 其他部分省略 //// ] }, { name:"城市", value: "商洛", children: [ /// 其他部分省略 //// ] } ] } ] }
- 测试广度优先搜索函数
let step = breadthFirstSearch(dataTree,"天河区"); console.log(`目标结点在图中的第 ${step} 层`);
