摘要：散列表上面的地图向我们展示了如何用广度优先搜索的思想找到北京到广州的最短路线。在广度优先搜索中，我们需要用到队列的这种思想来实现查找。建立了下面这个模型武汉广州西藏上海上海武汉广州代码完整实现，利用递归和广度优先搜索的思想实现。
什么是广度优先搜索？
如果只是是背概念，幼儿园的小朋友都能背下来念给你听。
假设看这篇文章的都和我一样是个前端工程师，我们要从广度优先搜索（BFS）中学到什么？如果你看完这篇文章能够回答这个问题，那么你已经看懂了。
广度优先搜索不是排序算法，它和快速排序、选择排序、冒泡排序等不一样，你听过二分查找吗？广度优先搜索是一种查找算法。
它可以用来解决2类问题：
1、节点A能不能到节点N？
2、如果能到，它的最短路径是什么？
我们将要了解到的知识1、图
2、散列表
3、队列
4、算法实现
图学过数据结构的同学对图比较了解了，没学过的也没关系，图表示的关系网络，你看过神经网络图、人际关系图、家族图谱图、以及最常见的地图吗？如果你都没见过，还是别学了......
下面我将展示一个简单的地图。
思考一个问题，假设你现在在北京，现在想跳槽到广州，行李以及收拾好了，跟老板辞职也通过了，现在你想将所有可以到达广州的路线找出来（这里忽略你搭地铁或者打的的时间，而且模拟北京不能直达广州的情况），都有那几条路线？
请思考1分钟....
确保你真的思考的前提下，我来猜一下你是如何找到北京到广州的所有路线的！
1、你眼睛先盯着北京，然后发现可以到达武汉，接着发现武汉可以到达广州，ok，第一条路线完成。
北京 -> 武汉 -> 广州
2、接着你又返回北京，你突然记得武汉可以到达上海，所以你又从北京到达了武汉，武汉去了上海，发现上海可以到达广州。第二条路线完成。
北京 -> 武汉 -> 上海 -> 广州
3、再次回到北京，你记得武汉还有一条去往西藏的路线，但是走了一遍发现西藏不能到达广州。
4、回到北京，现在出发去上海，接着你发现上海直接到达了广州，第三条路线完成。
北京 -> 上海 -> 广州
5、回到北京，再次去上海，接着到武汉，哇塞，又能到广州了。第四条路线完成。
北京 -> 上海 -> 武汉 -> 广州
现在找完了所有路线，一共4条，但是，这不是广度优先搜索的思路。不过已经很接近了，广度优先搜索没有那么深奥，你完全可以用正常逻辑来理解。
还记得上面我们说到广度优先搜索解决的问题吗？
1、节点A能不能到节点N？
2、如果能到，它的最短路径是什么？
广度优先搜索判断北京到广州的路径：
1、首先你在北京；
2、接着你问自己，北京能不能直接到达广州？你将地图搜索了一下，发现北京只能到达武汉和上海，这说明你完成了第一步搜索。上海和武汉属于北京的“一度空间”，具有优先搜索权；
3、西藏和广州属于北京的“二度空间”，当你在一度空间搜索不到目标时，就在二度空间搜索，如果还是搜索不到，就一直往N度空间搜索下去，直至搜索完整个地图。用正常人的理解就是，第2步时你搜索了武汉和上海都没有找到目标，就分别搜索武汉和上海的临近节点，发现武汉和上海都可以直接到达广州；
4、你根据这种方法很快就回答了广度优先搜索提出的2个问题，找到了北京到广州的路线，并且找到了2条可能是最短的路线：北京 -> 武汉 -> 广州，北京 -> 上海 -> 广州。实际问题中，我们需要计算的节点间的距离找到最短的路线，这里不做计算，只分析思路。
图本身的概念挺多，包括节点、边界、有向、无向，但不需要学习这些知识也能理解广度优先搜索的思想。
散列表上面的地图向我们展示了如何用广度优先搜索的思想找到北京到广州的最短路线。那么散列表是什么？它在广度优先搜索中的作用是什么？
为了回答这2个问题，我想请你回忆一下JavaScript中的Map，如果不了解Map，也没关系，回忆Object也行。Object近似的可以看成是散列表的数据结构。
散列表也叫做哈希表，它的平均时间复杂度是O(1)，它长的也不奇怪，就是key，value结构。
我们可以用简单的Object结构来表示节点之间的关系：
const map = {
"武汉": {
"广州": {},
"西藏": {},
"上海": {}
},
"上海": {
"武汉": {},
"广州": {}
}
}
散列表的内部实现是一种链组结构，也就是链表和数组的复合体。使用散列表的时候，要注意，key尽量不要重复，要分散，如果有重复，就会造成冲突，导致时间复杂度不是O(1)了。
队列有了图的存储结构，就能用代码来实现查找操作，但是在这之前，我们还要了解队列的思想。
你应该有过在学校饭堂排队打饭的体验，在确保没人插队的前提下，排队越前的就越先打到饭，然后离开，新来的要打饭的人必须排队到队列的末尾。专业名词叫做“先进先出”。
在广度优先搜索中，我们需要用到队列的这种思想来实现查找。JavaScript可以用数组模拟队列，你不需要多带带构建一个队列的数据结构。
算法实现那么，广度优先搜索是如何用队列实现的呢？
想要回答这个问题，我们结合前面讲过的图、散列表、队列一起来解答。
先要明白一点，广度优先搜索没有唯一的算法，不同的图实现的方法不一样，但是思想是一致的，主要跟你的图对应的存储结构有关。复杂的图可能使用多张表来存储数据。
这里我采用的方法是根据维度空间来建立数据模型。首先找到一维空间的路线，北京 -> 武汉，北京 -> 上海。然后是二维空间的路线。建立了下面这个模型：
const map = {
"武汉": {
"广州": {},
"西藏": {},
"上海": {}
},
"上海": {
"武汉": {},
"广州": {}
}
}
JavaScript代码完整实现，利用递归和广度优先搜索的思想实现。
思路：构造二度空间散列表，我们只需要遍历一度空间，然后用递归遍历二度甚至N度空间即可，但是递归要注意内存溢出的问题，前端不宜做大量数据的算法操作。
const map = {
"武汉": {
"广州": {},
"西藏": {},
"上海": {}
},
"上海": {
"武汉": {},
"广州": {}
}
}
function breadthSearch(obj, goal, arr = ["北京"]) {
for(let key in obj) {
//遍历一度空间
if (arr.indexOf(key) < 0) {
//如果数组中不存在当前的key，就push
arr.push(key)
if (key === goal) {
//如果key是要查找的目标节点，直接返回
return arr
} else {
//如果key不是要查找的目标节点，继续递归
return breadthSearch(obj[key], goal, arr)
}
}
}
}
const s = breadthSearch(map, "广州")
console.log(s) //["北京", "武汉", "广州"]
总结
看到这里，广度优先搜索的思想以及JavaScript模拟实现到这里就结束了，前端工程师不需要完全掌握它，而是学会分析这种问题，思维比算法的实现更重要，如果给你换一个图，你就不会用JavaScript实现也没有关系，能用文字表达出思路就够了。
广度优先针对的是无权图的搜索，如果给节点之间的边加上权重距离，就要用到其他算法了，后面我会讲到狄克斯特拉算法和贪婪算法等思想的实现。
与广度优先搜索相对的，就是深度优先搜索，我不打算在这一章讲，回到文章一开始的问题，你从广度优先搜索（BFS）中学到了什么？现在能回答了吗？
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/89738.html
摘要：散列表上面的地图向我们展示了如何用广度优先搜索的思想找到北京到广州的最短路线。在广度优先搜索中，我们需要用到队列的这种思想来实现查找。建立了下面这个模型武汉广州西藏上海上海武汉广州代码完整实现，利用递归和广度优先搜索的思想实现。 什么是广度优先搜索？ 如果只是是背概念，幼儿园的小朋友都能背下来念给你听。 假设看这篇文章的都和我一样是个前端工程师，我们要从广度优先搜索（BFS）中学到什么...
摘要：邻接矩阵在邻接矩阵实现中，由行和列都表示顶点，由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连如果相连这个值表示的是相连边的权重。直到返回到顶点完成探索具体还有版的深度和广度优先的算法，具体代码奉上直达地址 图github直达地址 https://github.com/fanshyiis/... 在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆...
摘要：存在好几种方式来表示这种数据结构。下面的示意图展示了邻接表数据结构。在关联矩阵中矩阵的行表示顶点列表示边。广度优先搜索算法和深度优先搜索算法基本上是相同的只有一点不同那就是待访问顶点列表的数据结构。 1 树 一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶部的第一个节点)以及零个或多个子节点。位于树顶部的节点叫作根节点(11)。它没有父节点。树中的每个元素都叫作...
摘要：不撞南墙不回头深度优先搜索基础部分对于深度优先搜索和广度优先搜索，我很难形象的去表达它的定义。这就是深度优先搜索了，当然，这个题目我们还有别的解法，这就到了我们说的广度优先搜索。 不撞南墙不回头-深度优先搜索 基础部分 对于深度优先搜索和广度优先搜索，我很难形象的去表达它的定义。我们从一个例子来切入。 输入一个数字n，输出1~n的全排列。即n=3时，输出123，132，213，231，...
摘要：广度优先搜索上一次已经提到，图的遍历一般有两种算法，即广度优先和深度优先。其中广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层。其它最短路径算法对于加权图的最短路径，广度优先算法可能并不合适。 广度优先搜索（BFS） 上一次已经提到，图的遍历一般有两种算法，即广度优先和深度优先。其中广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的...
阅读 1319·2021-09-22 15:52
阅读 3256·2021-09-22 14:59
阅读 2664·2021-09-02 15:12
阅读 812·2021-08-20 09:35
阅读 1447·2019-08-30 14:09
阅读 2601·2019-08-30 13:56
阅读 1441·2019-08-26 18:27
阅读 3222·2019-08-26 13:37
