爬虫进阶-2-广度优先算法和深度优先算法

爬虫进阶-2-广度优先搜索和深度优先搜索

本文中介绍的是爬虫的两种常见算法，当然它们不仅仅是运用在爬虫中：

• 广度优先搜索
• 深度优先搜索

它们是图的基本搜索算法，主要区别在于搜索顺序不同，解决的是图的最短路径问题。

图

下面的圆圈称之为结点或者顶点，连接顶点的线叫做边。

顶点和连接顶点的边构成的图形就是图

图的各种应用：

• 各种社交网络关系
• 交通网络图，比如地铁运营图
• 计算机网络图

加权图

如果我们给不同的边加上一个值，这个值称为边的“权重”或者“权”，这样的图就称为“加权图”。

有向图

当我们给各个顶点之间加上箭头，表示方向，这样的图就称为“有向图”。

有向图也可以有权重；

广度优先搜索

1、从顶点开始

2、选择最早成为候补的那个顶点，如果有多个，随机选择一个

整个搜索的顺序：A、B、C、D、E、F、H、I、J、K、G、L

深度优先搜索

深度优先搜索会沿着一条路径搜索到不能再继续为止，然后再折返，开始搜索下一条候补路径。

整个的搜索顺序为：A、B、E、K、F、C、H、G、D、I、J、L

二者区别

区别

广度优先搜索选择的是最早成为候补的顶点，因为顶点离起点越近就越早成为候补，所以会从离起点近的地方开始按顺序搜索；

而深度优先搜索选择的则是最新成为候补的顶点，所以会一路往下，沿着新发现的路径不断深入搜索。

举例

比如某个在线网站的课程有如下的介绍，用户可以学习不同的语言：Python、Node.js、Golang。一般都是两种学习方式

（1）、先把一门语言学完

比如学习Python，Python到爬虫到课时1、课时2、课时N，再学习Django，再学习机器学习；学完Python，再学Node.js，从基础知识到Express；再学习Golang的基础知识，再学习并行计算。

这种方式就是深度优先搜索

（2）、同时学习多门语言

如果用户是按照Python---Node.js---Golang---爬虫---Django---机器学习---基础知识---Express---基础知识---并行计算---课时1（爬虫）---课时2（爬虫）的学习路线：

这种方式就称为广度优先搜索。比如我们爬取某个贴吧中的内容，爬取某个帖子的最近的内容，爬取它的每个楼层