定义：广度优先搜索让你能够找到两样东西之间的最短距离。
例如：
1.下棋时，计算走最少多少步就可以获胜。
2.根据人际关系网找到最近的医生。

图简介

你需要从双子峰到金门大桥
image.png
你需要找到换成最少的乘车路线，这了问题被称为最短路径问题。解决最短路经的算法被称为广度优先搜索。
解决这类问题需要两个步骤：
1.使用图建立问题模型。
2.使用广度优先搜索解决问题。

图是什么

图模拟一组链接。

广度优先搜索

广度优先搜索是一种用于图的查找算法，可帮助回答两类问题。
1.从A出发，有到B的路经吗？
示例：你是有一个芒果农场，你需要寻找芒果销售商，把芒果卖给他。在facebook，你与芒果销售商有联系吗？
答：首先你需要把通讯录加入列表遍历是否存在芒果经销商，
如果没有，你则需要在朋友的朋友中查找，以此类推。
这就是广度优先搜索算法。

2.从A出发，到B哪条路经最短？
示例：谁是关系最近的芒果经销商？
朋友是一度关系，朋友的朋友是二度关系，一度胜过二度，以此类推。
那需要将首先查找一度关系，再查找二度关系，按顺序进行检查，可以实现这种目的的数据结构就是队列。

队列

列队支持两种操作：入队和出队。
队列是一种先进先出的数据结构，而栈是一种后进后出的数据结构。

实现图

用代码实现图，图由多个节点组成。
每个节点都与邻近节点相连，这种就是散列表。

  1. let graph = {};
  3. graph['you']=['alice','bob'];
  4. graph['alice']=['thom','jonny'];
  5. graph['bob']=['anuj','peggy'];

实现算法

工作原理：
1.创建一个队列，用于存储需要检查的人
2.从队列中弹出一个人
3.检查这个人是否是芒果销售商
4.a.成功
4.b.否将这个人通讯录中的人加入队列
5.回到第二步
6.如果队列为空，就说明你的人际关系网中没有芒果销售商。

  1. const graph = {
  2.   'alice': {
  3.     'jonny': {},
  4.     'thom': {}
  5.   },
  6.   'bob': {
  7.     'anuj': {},
  8.     'peggy': {}
  9.   }
  10. }
  12. function breadthSearch(obj, goal, arr=['you']) {
  13.   for(let key in obj) {
  14.     //遍历一度空间
  15.     if (arr.indexOf(key) < 0) {
  16.       //如果数组中不存在当前的key，就push
  17.       arr.push(key)
  18.       if (key === goal) {
  19.         //如果key是要查找的目标节点，直接返回
  20.         return arr
  21.       } else {
  22.         //如果key不是要查找的目标节点，继续递归
  23.         return breadthSearch(obj[key], goal, arr)
  24.       }
  25.     }
  26.   }
  27. }
  29. const s = breadthSearch(graph, 'peggy')
  31. console.log(s) //["you", "bob", "peggy"]

运行时间

广度优先搜索的运行时间为O（顶点数+边数） ，写作（V+E）。