广度优先-BFS

  遍历是指从某个节点出发，按照一定的搜索路线，依次访问对数据结构中的全部节点，且每个节点仅访问一次。

在二叉树基础中，介绍了对于树的遍历。树的遍历是指从根节点出发，按照一定的访问规则，依次访问树的每个节点信息。树的遍历过程，根据访问规则的不同主要分为四种遍历方式：

（1）先序遍历

（2）中序遍历

（3）后序遍历

（4）层次遍历

  类似的，图的遍历是指，从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。遍历过程中得到的顶点序列称为图遍历序列。

图的遍历过程中，根据搜索方法的不同，又可以划分为两种搜索策略：

（1）深度优先搜索（DFS，Depth First Search）

（2）广度优先搜索（BFS，Breadth First Search）

广度优先搜索

算法思想

  广度优先搜索思想：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

广度优先

  DFS，BFS 在搜索引擎中的应用我们几乎每天都在 Google, Baidu 这些搜索引擎，那大家知道这些搜索引擎是怎么工作的吗，简单来说有三步：

1、网页抓取

  搜索引擎通过爬虫将网页爬取，获得页面 HTML 代码存入数据库中

2、预处理

  索引程序对抓取来的页面数据进行文字提取，中文分词，(倒排)索引等处理，以备排名程序使用

3、排名

  用户输入关键词后，排名程序调用索引数据库数据，计算相关性，然后按一定格式生成搜索结果页面。

  我们重点看下第一步，网页抓取。

  这一步的大致操作如下：给爬虫分配一组起始的网页，我们知道网页里其实也包含了很多超链接，爬虫爬取一个网页后，解析提取出这个网页里的所有超链接，再依次爬取出这些超链接，再提取网页超链接。。。，如此不断重复就能不断根据超链接提取网页。如下图示：

如上所示，最终构成了一张图，于是问题就转化为了如何遍历这张图，显然可以用深度优先或广度优先的方式来遍历。

如果是广度优先遍历，先依次爬取第一层的起始网页，再依次爬取每个网页里的超链接，如果是深度优先遍历，先爬取起始网页 1，再爬取此网页里的链接...，爬取完之后，再爬取起始网页 2...

实际上爬虫是深度优先与广度优先两种策略一起用的，比如在起始网页里，有些网页比较重要(权重较高)，那就先对这个网页做深度优先遍历，遍历完之后再对其他(权重一样的)起始网页做广度优先遍历。

DFS 和 BFS 是非常重要的两种算法，本文为了方便讲解，只对树做了BFS，大家可以试试如果用图的话该怎么写代码，原理其实也是一样，只不过图和树两者的表示形式不同而已，DFS 一般是解决连通性问题，而 BFS 一般是解决最短路径问题