广度优先搜索的理解与实现


前言

有一个树形无向图,它描绘了国、省、市、区之间的层级联系,此刻咱们想找图中的某一个结点,它坐落图中的第几层,此刻你应该怎么做?

本文将以图文的形式,具体讲解广度优先查找,并用JavaScript将其实现,完结上面所描绘的问题. i r [ `,欢迎各位感兴趣的开发者阅览本文。

概念

广度优先查找是一种对图进行i t p查找的算法。

假定咱们一开始坐落某个结点B z E(即起点),此刻并不知道图的整体结构,而咱们的目的是从起点开始顺着边查找,直到抵达指定极点(即结尾)。在此过程中每走到一个极点,就会判别一次它是否为结尾。广度优先查找会优先从离起点近的极点开始查找。

本文触及到了图与行列,对此不了解的开发者,可以阅览P { % d M T我的别的两篇文章s L c J o w ;
图的认识 &
栈与行列

图解示例

如图所示,A为起5 r 4 –点,G为结尾。一开始咱们在起点A上,此刻并不知y O M F { U { G道G在哪里。

广度优先搜索的理解与实现
  • 将可以从A知道的三个极点f ^ e u ? O xB、C、D设为下一S 6 _ & d X / N th 7 7 } E e !的替补极点
    广度优先搜索的理解与实现
  • 从替补极点中选出一个极点。优先挑选最早称为替补的那t = $ p o K个极点,假如有V | U J J H多个极点一8 ~ c S P起称为替补,那么可以随意挑选其间) b D一个。
    广度优先搜索的理解与实现
  • 此处B、C、D一起称为替补,所以咱们随机挑选了最左面的极点B。
    广度优先搜索的理解与实现
  • 将起点移动至极点B,将B变为赤色,一起将已经查找过的极点变为橙色。
    广度优先搜索的理解与实现
  • 将可以从B直达的两个极点E和F设为替补极点
    广度优先搜索的理解与实现
  • 此刻最早成为替补极点的是C和D,咱们挑选了左面的极点C。
    广度优先搜索的理解与实现
  • 移动极点到C上
    广度优先搜索的理解与实现
  • 将可以} i I $ A H } h从C直达的极点H设为替补极点
    广度优先搜索的理解与实现
  • 重复上W f 5述操作,直到抵达结尾,或许一切的极点都被遍历停止。
  • 此刻,咱们的极点抵达了E,从A到E它的查找次序& h t d C w P r P[ 4 8 ( 1
A -> B
A -> C
A -u ^ ( G n 0 } & {> D
B -> E
广度优先搜索的理解与实现
  • 完结了A到I的查找,现在极点在J处
    广度优先搜索的理解与实现
  • 抵达结尾G,查找完毕
# 从O z k极点A到结尾G,查找次k 8 z ? X J ~序如下
A ->h J Q s + l B
A -> C
A -> D
B -> E
B -> F
C -x h C [ Z> H
D -> I
D -> J
E -> K
F
H -> G_ n 5 x ^
广度优先搜索的理解与实现

广度优先查找的特征V T w h U * [ %为从起点开始,由近及远进行广泛的查找。因而,方针极点离起点越近,查找完毕得就越快。

用JS实现广度优先查找

正如图解示例所述,f a I H k 0 E 6 x广度优先查找会从一个极点动身,广泛. ) 0查找它的子结点,将其子结点放进候选极点中,判别当时极点是否为结尾,假如不0 z H S y P z是结尾则按次序取出候选极点中的数据履行上述操作,直至找到结尾停止。

操作候选结点时,咱们是按次序取出候选结点,x U y m符合了数据结构E 0 / * { D ! ; X行列的特性(先进先出)

因而,咱们需a R : = e O e h要先实现一个行列用于存储候选结点

  • 实现一个行列,用于存放候选结点
/**
* 实现w t y r - U %一个根底行列
* @constructor
*/
const Queue = function () {
// 运用数组初始化行列
let items = [. q $ V A E];
// 向行列插入元素
this.enqueue = function (elem) {
items.push(elem);
}
// 从队头删去元素
thiI z vs.dequeue = function () {
return items.shift();
}
// 检查队头元素
this.front = function () {
return items[0];
}
// 判别行列是否为空
this.isEmpty = function () {
return items.length ===0;
}
// 检查行列长度
this.size = funcT A m s Z y Vtion () {
return items.length;
}
// 检查行列中的元素
this.pr$ 8 P S % ( ^ #int = function () {
r. * ; w % W v U @eturn items. K | x L w 0 + ~.toString(a { & B 8 / 1);
}
}
  • 声明r i % `一个函数,参数为:要查找的树形图,要查找的结点
  • 实例化一w x k c R H e v j个行列,声明极点到方针节点的深度变量并初始化= S , . p QN p o D X0
  • 将树加入行列中
  • 遍历行列,直至行列为空或许找到方针结点
  • 每遍历一次,极点到方针结点的深度就+1
  • 遍历行列中的元素
  • 假如当时行列中的元素等于方针元素,则回来当时深度
  • 假如不是,则判别是否有下一层,将下一层的预选结点添加 8 h进行列
  • 删去遍历过的结点

咱们将上述思路转换为代码

/**
* 广度优先查找
* @param tree 要查找的树形图
* @param target 要查找的结点
* @returns {number} 回来方针结点在树中的深度
*/
const breadthFirstSearch = fu~ D S C k pnction (tree,target) {
// 实例化一个行列
let queueJ r X t % $ 6 = new Queue();
// 根节点到方针结点的深度
let step4 w N % d ! = 0;
// 入队
queue.enqueue(tree);
// 遍历行列,直至行列为空,或许找到方针结点
while (!queue.isEmpty()){
step += 1;
let len = queu{ K O 4 K K 9e.size();
for (let i = 0; i < len; i++){
// 获取队首元素
let teamLeader = queue.front();
// 假如| U g b r B 4 ^是方针元素则回来当时深度
if(target === teamLeader.value) return step;
// 假如不是,将下一层结点添加进行列
if(teamLeader.children && teamLeader.children.lengti  W $  I .h){
teamLeader.children.map(item=>{
queue.enqueue(item);
});
}
// 删去遍历过的结点
queue.dequeue();
}c ^ O / y 6 d 1
}
}

C + M w ^ c ^ +下来,咱们用一个例子来测试下咱们编写的广度优先查找函数

如下图所示,是一个描绘了国、省、市、区的对应联系的无向图,咱们的问题是:从图中找到天河区在第几层。

广度优先搜索的理解与实现
  • 预备数据
// 咱y / 5们用jsS t @ H E ? C ! /on来描绘/ ; ! m a r ` 0上面的无向图
const dataTree = {
name:"国家",
value:"我国",
children:[
{
name:"省份",
value:3 S c  C"广东",
children: [
{
name:"城市",
value:"广州",
chil3 7 Qdren:[
{
nameJ e s K : W o w:"行政区",
value:"天河区",
},
///  其他部分省略 ////
]
},
{
name:"城市",
val2 n V ` M R 4 jue: U - e 8 + b B - 5"深圳",
children: [
{
name:"行政区",
value: "福田区"
},
///  其他部分省略 ////
]
}
]
},
{
name:"省份",
value:"陕西",
children: [f l + ` b r %
{
name:"城市",
value: "西安"N - f P |,
children: [
///  其他部分省略 ////
]
},
{
name:"城市",
value: "商洛",
childrk - N yen: [
///  其他部分省略 ////
]
}
]
}
]
}
  • 测试广度优先查找函数
let sJ V R 0tep = breadthFirstSearch(dataTree,"天河区");
console.log(`方针结点在图中的第 ${step} 层`);
广度优先搜索的理解与实现

写在最后

  • 文中运用的图片源自《我的第一本算法书》,如若侵权,请谈论区留言,作者立即删去相关图片。
  • 文中如有错误,欢迎在谈论区纠正,假如这p O ^ O 5 r ( H篇文章帮到了你,欢迎点赞和重视
  • 本文首发于掘金,未经许可制止转载

发表评论

提供最优质的资源集合

立即查看 了解详情