什么是广度优先搜索？如果只是背概念，幼儿园的孩子可以背下来读给你听。假设看这篇文章的各位都是和我一样的前端工程师，那么我们应该从广度优先搜索（BFS）中学到什么？如果看完这篇文章你能回答这个问题，那你就明白了。广度优先搜索不是排序算法。它不同于快速排序、选择排序、冒泡排序等。你听说过二分查找吗？广度优先搜索是一种搜索算法。它可以用来解决两类问题：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个问题，找到了北京到广州的路线，找到了2条可能的最短路线：北京->武汉->广州，北京->上海->广州。在实际问题中，我们需要计算节点之间的距离来寻找最短路线。我们这里不做计算，只分析思路。图本身有很多概念，包括结点、边界、有向、无向，但是不用学这些知识也能理解广度优先搜索的思想。哈希表上方的地图向我们展示了如何使用广度优先搜索的思想来找到从北京到广州的最短路线。那么什么是哈希表呢？它在广度优先搜索中的作用是什么？为了回答这两个问题，我想请大家回忆一下JavaScript中的Map。如果你不懂Map，没关系，你也可以回忆一下Object。对象可以看作哈希表的数据结构。哈希表也称为哈希表。它的平均时间复杂度是O(1)，长这样也就不足为奇了。它是一个键值结构。我们可以用一个简单的Object结构来表示节点之间的关系：constmap={'Wuhan':{'Guangzhou':{},'Tibet':{},'Shanghai':{}},'Shanghai':{'武汉':{},'广州':{}}}哈希表内部实现是链式结构，是链表和数组的复合体。使用哈希表时要注意键尽量不要重复，要分散。如果有重复，就会造成冲突，导致时间复杂度不是O(1)。有了图的存储结构，队列就可以使用代码实现查找操作了，不过在此之前，我们需要了解一下队列的思想。你应该有过在学校食堂排队吃饭的经历吧。在保证无人插队的前提下，先排队的先吃完饭，然后离开。新人想要吃到饭，必须排到队尾。技术术语称为“先进先出”。在广度优先搜索中，我们需要使用队列的思想来实现搜索。JavaScript可以使用数组来模拟队列，不需要单独构建队列数据结构。算法实现那么，广度优先搜索是如何用队列实现的呢？为了回答这个问题，我们结合上面提到的图、哈希表和队列来回答。首先要明白，广度优先搜索没有唯一的算法，不同的图实现的方法不同，但是思路是一样的，主要跟你的图对应的存储结构有关。复杂的图可能使用多个表来存储数据。我这里采用的方法是基于维度空间构建数据模型。先在一维空间找路线，北京->武汉，北京->上海。然后是二维空间中的路线。建立如下模型：constmap={'武汉':{'广州':{},'西藏':{},'上海':{}},'上海':{'武汉':{},'广州'：{}}}JavaScript代码完全实现，使用递归和广度优先搜索的思想。思路：构造一个二维空间哈希表，只需要遍历一次空间，然后用递归遍历二次甚至N次空间。但是递归要注意内存溢出的问题，前端不适合对大量数据进行算法运算。constmap={'武汉':{'广州':{},'西藏':{},'上海':{}},'上海':{'武汉':{},'广州':{}}}functionbreadthSearch(obj,goal,arr=['北京']){for(letkeyinobj){//遍历一次空间if(arr.indexOf(key)<0){//如果没有当前key，直接pusharr.push(key)if(key===goal){//如果key是要查找的目标节点，直接returnreturnarr}else{//如果key不是要查找的目标节点搜索，继续递归返回breadthSearch(obj[key],goal,arr)}}}}consts=breadthSearch(map,'广州')console.log(s)//["北京","武汉","广州"》]总结看到这里，广度优先搜索的思想和JavaScript模拟实现到这里就结束了。前端工程师不需要完全掌握，而是学会分析这类问题。思维比算法实现更重要。如果你换了一张图片，不知道用JavaScript实现也没关系，用文字表达你的想法就够了。广度优先旨在搜索未加权的图。如果将权重距离添加到节点之间的边缘，则需要使用其他算法。后面会讲到Dijkstra算法、贪心算法等思想的实现。与广度优先搜索相反的是深度优先搜索。我不打算在本章中谈论它。回到文章开头的问题，你从广度优先搜索（BFS）中学到了什么？我现在可以回答吗？
