有一个树形无向图,它描述了国、省、市、区之间的层级关系,此时我们想找图中的某一个结点,它位于图中的第几层,此时你应该怎么做?
本文将以图文的形式,详细讲解广度优先搜索,并用JavaScript将其实现,完成上面所描述的问题,欢迎各位感兴趣的开发者阅读本文。
广度优先搜索是一种对图进行搜索的算法。
假设我们一开始位于某个结点(即起点),此时并不知道图的整体结构,而我们的目的是从起点开始顺着边搜索,直到到达指定顶点(即终点)。在此过程中每走到一个顶点,就会判断一次它是否为终点。广度优先搜索会优先从离起点近的顶点开始搜索。
本文涉及到了图与队列,对此不了解的开发者,可以阅读我的另外两篇文章:图的认识 &栈与队列
如图所示,A为起点,G为终点。一开始我们在起点A上,此时并不知道G在哪里。
A -> B
A -> C
A -> D
B -> E
# 从顶点A到终点G,搜索顺序如下
A -> B
A -> C
A -> D
B -> E
B -> F
C -> H
D -> I
D -> J
E -> K
F
H -> G
❝广度优先搜索的特征为从起点开始,由近及远进行广泛的搜索。因此,目标顶点离起点越近,搜索结束得就越快。 ❞
正如图解示例所述,广度优先搜索会从一个顶点出发,广泛搜索它的子结点,将其子结点放进候选顶点中,判断当前顶点是否为终点,如果不是终点则按顺序取出候选顶点中的数据执行上述操作,直至找到终点为止。
操作候选结点时,我们是按顺序取出候选结点,符合了数据结构:「队列的特性」(先进先出)
因此,我们需要先实现一个队列用于存储候选结点
/**
* 实现一个基础队列
* @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();
}
}
❝我们将上述思路转换为代码 ❞
/**
* 广度优先搜索
* @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} 层`);