什么是广度优先搜索？

如果只是是背概念，幼儿园的小朋友都能背下来念给你听。

假设看这篇文章的都和我一样是个前端工程师，我们要从广度优先搜索（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）中学到了什么？现在能回答了吗？

大多数开发者应该都遇到过在mysql字段中存储逗号分割字符串的经历，无论这些被分割的字段代表的是id还是tag，这个字段都应该具有如下几个共性。

• 被分割的字段一定是有限而且数量较少的，我们不可能在一个字符串中存储无限多个字符
• 这个字段所属的表与这个字段关联的表，一定是一对多的关系

比如下面这个表结构所代表的content与tag这两个对象

mysql> SELECT * FROM content;
+----+------+
| id | tags |
+----+------+
|  1 | 1,2  |
|  2 | 2,3  |
+----+------+
2 rows in set (0.01 sec)

mysql> SELECT * FROM tag;
+----+-------+
| id | name  |
+----+-------+
|  1 | php   |
|  2 | mysql |
|  3 | java  |
+----+-------+
3 rows in set (0.00 sec)

这些原则问题，相信大家在开发过程中已经很熟悉了。但是你在使用这种方法来处理实际问题时，内心一定还是有些许忐忑，因为这种方法或多或少看上去有点像野路子。在那本厚厚的《数据库》教材中，也没有提到这种设计方法，标准的方法似乎是应该使用一个关系映射表在这两个表之间插一杠子，尽管这样会使用效率低下的连接查询。

每个开发者都曾纠结于标准与效率，但我想我们的努力能使这种方法的使用看起来更加标准。注意，以下讨论的使用方法仅限于mysql，但其它数据库应该可以移植。

<h3>相关性检索</h3>

很多开发者还在使用古老的LIKE方法来实现相关性检索，比如上面那个数据库结构中，content表中的两条记录都有2这个tag，那么怎样在我取出记录1时，把与它tag相关的记录也显示出来呢。其实这也是CMS需要面对的一个基本问题，也就是相关内容的查询。

如果你是一个菜鸟，你可能只会想到LIKE方法，比如先把记录1取出来，然后再把tags字段按逗号分割，最后做一个循环用LIKE检索content表中所有tags字段中包含2的记录，类似这样

SELECT * FROM content WHERE tag LIKE '%2%' AND id <> 1

但这种方法实在是太慢了，查询次数多不说，LIKE查询本来就是一个比较慢的方法。而且你还要处理前后逗号的问题，总之麻烦是一大堆。

所以让我们静下心来翻翻mysql手册，看看有没有什么惊喜。这个时候，一个名为FIND_IN_SET的函数，会闪着金光映入你的眼帘。让我们看看这个函数的定义

<blockquote>
FIND_IN_SET(str,strlist)

Returns a value in the range of 1 to N if the string str is in the string list strlist consisting of N substrings. A string list is a string composed of substrings separated by “,” characters. If the first argument is a constant string and the second is a column of type SET, the FIND_IN_SET() function is optimized to use bit arithmetic. Returns 0 if str is not in strlist or if strlist is the empty string. Returns NULL if either argument is NULL. This function does not work properly if the first argument contains a comma (“,”) character.
</blockquote>

哦，PERFECT! 简单说来就是寻找一个字符串是否在另一个以逗号分割的字符串中存在的函数，这简直是为我们量身定做的。那么我们的sql就变成

SELECT * FROM content WHERE FIND_IN_SET('2', tags) AND id <> 1

在翻这些函数的过程中，你应该已经深深地体会到mysql的设计者对以逗号分割存储字段方法的肯定，因为有很多方法就是设计用来处理这种问题的。

这样看起来好多了，一切似乎完美了，是这样吗？其实还没有，如果你的tag比较多，你需要创建多个sql语句，而且有的记录关联的tag比较多，有的比较少，怎么能按照相关性进行排列呢。

这个时候，你可以关注mysql的全文检索功能。这个词你肯定看见过无数回了，但是这么使用的肯定很少，让我们直接看语句吧

SELECT * FROM content WHERE MATCH(tags) AGAINST('1,2') AND id <> 1

这个语句的优势是显而易见的，你不需要对tags字段做再次分割。那么这种查询的原理是什么呢，稍微了解下MATCH AGAINST的用法就知道，全文检索的默认分隔符是标点符号和stopwords，其中前者正是我们需要的特性。全文检索按照逗号将MATCH和AGAINST里的字符串做分割，然后将它们匹配。

需要注意的是上面sql仅仅是个例子，如果你直接这么执行，是无法得到任何结果的。原因在以下

<ol>
<li>你需要对tags字段建立fulltext索引（如果仅仅是测试，可以不做，建索引只是提高性能，对结果没有影响）</li>
<li>每个被标点符号分割的word长度必须在3个字符以上，这才是关键，我们的tag id太短了，会被自动忽略掉，这个时候你可以考虑让id从一个比较大值开始自增，比如1000，这样它就够长了。</li>
<li>你撞到了stopwords，比如你的tags字段是这样的'hello,nobody'，nobody是mysql的一个默认的stop words，它会被自动忽略。stop words是英文中的一些无意义词，搜索的时候不需要它们，类似汉语中的助词等等。但在我们的使用中显然不是用来做搜索的，因此可以在my.cnf文件里，加上ft_stopword_file=''来禁用它</li>
</ol>

随着WEB技术的发展，相关搜索走SQL的情况越来越少，很多时候只需要用搜索引擎就可以了。但本文的目的并不只是讨论这种方法，而是体现实现这一结果的过程。

Beta1.官方说明
Beta2.官方说明

2.x 版本的vue-router相比之前的0.7.x版本，有很多破坏性改变：

通用 API 的修改

• 旧的 router.go() 现在改成了 router.push().

• 新的 router.go 类似 window.history.go(): 接受一个数值作为参数在历史栈中导航

• 新增的方法:

  • router.back()

  • router.forward()

路由配置

所有路由配置都通过一个单独的对象传到Router的构造函数。所以可用的选项，参见configuration object's type declaration。

routes 选项取代了 router.map()。此外，路由配置现在用数组而不是用对象哈希表来作为数据结构。这保证了一致的匹配次序（对象键值枚举的次序是依赖浏览器的实现的）。

这里 是一个新的配置语法的例子.

以下的路由器实例配置选项被作废了：

• history (被 mode 取代)

• abstract (被 mode 取代)

• root (被 base 取代)

• saveScrollPosition (被 scrollBehavior 取代，后者用起来更加灵活，下面会提到)

• hashbang (因为 hashbang 在Google爬站的时候不再需要，所以移除了此选项)

• transitionOnLoad (因为 Vue 2.0 有显式的视觉表现过渡动画控制，所以此选项移除)

• suppressTransitionError (因为钩子函数的系统的简化而移除)

新的mode选项取值为： (默认是 "hash"):

• "abstract"

• "hash"

• "history"

在不支持 history.pushState 的浏览器中, 路由器会自动回退为 hash 模式.

下列方法已经作废：

• router.map (被 routes 选项取代)

• router.beforeEach (被 beforeEach 选项取代，不过 beta2中有修改，见下面)

• router.afterEach (被 afterEach 选项取代，不过 beta2中有修改，见下面)

• router.redirect (现在可以在 routes 中直接声明, 参见 Example)

• router.alias (现在可以在 routes 配置中直接声明, 参见 Example)

Beta 2 中，beforeEach 和 afterEach 又被改回成为 router的实例方法。作者说是这可以让插件和模块更加方便的在router实例创建后增加hooks。

导航钩子函数

钩子系统被极大简化，所有0.7的迁移钩子都作废了，下面是替代方案：

• 使用组件自身的生命周期钩子函数来替代activate 和 deactivate

• 在$router 上使用 watcher 来响应路由改变 (e.g. 比如基于新的路由参数获取数据 - Example)

• canActivate 可以被router 的配置中的 beforeEnter 中实现 Example

• canDeactivate 已经被 beforeRouteLeave 取代, 后者在一个组件的根级定义中指定。这个钩子函数在调用时是将组件的实例作为其上下文的。Example

• canReuse 已经被移除，因其容易混淆且很少被用到。

此外，在2.0版本中所有的钩子函数都有相同简洁的签名：

guard (toRoute, redirect, next) {
  // call redirect to redirect to another route
  // call next to confirm current route
  // or do nothing to cancel the navigation
}

这些函数也不再支持返回 Promises.

链接（Links）

v-link 指令已经被 <router-link> 组件替代. 这个组件接受以下属性参数:

• to: 一个路径字符串, 或者一个 Location Descriptor 对象.

• tag: 渲染为的 html 元素类型，默认是<a>.

• exact: 用于控制当前激活项的匹配行为（严格匹配或者贪婪匹配）.

• append: 控制相对链接路径的追加方式

• replace: 替代而不是作为历史条目压榨你

• active-class: 当链接项激活时增加的 CSS 样式

这里有个 复杂的例子 展示了<router-link>的用法。

命名视图 (Named Views)

单个路由现在可以映射到多个命名组件。这些组件将会在渲染在对应命名的多个 <router-view>中. Example
(译者注）这个功能很赞，提供了一种新的用多个组件组成页面结构的方法，同时又不增加组件之间的耦合。

滚动行为（Scroll Behavior）

scrollBehavior 选项接受一个函数，返回在路由导航时控制页面如何滚动的规则。你可以代码控制是否要滚动的页面顶部、书签或者在状态中保存的位置。 Example

Beta2 版本中又对 scrollBehavior 做了修改:

beta.1 中返回 { hash: true } 来滚动到文档中的一个锚点，现在返回的是 { selector: route.hash }。这也同时意味着你可以返回任意的 CSS 选择器，来匹配成要滚动到的目标。

此外，你还可以返回{ selector: '...', x: 0, y: 0 }，这会让路由器首先尝试滚动到匹配的元素，如果没有找到匹配元素，那就滚动到 x和y指定的位置。