前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >爬虫课程(四)|深度优先和广度优先算法

爬虫课程(四)|深度优先和广度优先算法

作者头像
黄小怪
发布2018-05-21 17:15:54
2.3K0
发布2018-05-21 17:15:54
举报
文章被收录于专栏:小怪聊职场

深度优先和广度优先算法在爬取一个整站上经常用到,本课程主要讲解这两个算法的原理以及使用过程。

一、网站的树结构

1.1、一个网站的url结构图

以知乎为例,知乎目前有发现、话题、Live、书店、圆桌、专栏主要的6个tab页。每个网站的url都是有一定的层次,如下图:发现explore、话题topic、Live lives、书店pub、圆桌roundtable、专栏zhuanlan都是在主域名zhihu的下一级,而具体的Live在zhuhu.com/lives/770340328338104320,内容又在话题之下zhihu/question/67006058/answer/250037350,网站的所有内容都一层一层的类似一个树形结构。

知乎网站的url结构图

1.2、网站url链接的结构图

当然,如果我们要做爬取整个网站的url时,我们必须要知道每个网站的url链接一般情况下都是存在环路的,也就是在下一级页面存在上一级页面的url链接,这样形成一个环路。当遇到这个情况时我们需要做url去重,一般的处理方式是把已经爬过的url放到一个list,每次爬取url的时候都去这个list查看下是否已经爬过,爬过的就跳过。这块url去重我下次再详细介绍。

url链接存在环路

二、深度优先和广度优先算法原理介绍(以二叉树为例)

为了更加容易理解深度优先和广度优先算法的原理,我们把一个网站的Tab理解成一颗树的节点,如下图:

二叉树

2.1、深度优先算法

如果我们从深度优先算法来遍历这棵树的节点,那么遍历的顺序是ABDECFHG。

深度优先遍历也叫深度优先搜索(Depth First Search)。它的遍历规则:不断地沿着顶点的深度方向遍历。顶点的深度方向是指它的邻接点方向。

从A开始遍历。

遍历分析:A有两个邻接点B和C,选择下标小的B遍历。接着从B开始深度遍历,B有两个邻接点D和E,选择下标小的D开始深度遍历,D下面没有邻接点,那么回溯到B深度往右遍历到E,E下面没有邻接点。至此,遍历得到的值为ABDE。EDB下的节点都遍历完之后就会从C开始深度遍历,同理遍历得出的值为CFHG。那么最后得出的结果为ABDECFHG。

使用Python代码实现的伪代码如下:

深度遍历算法

从代码可以知道深度优先算法是使用递归实现的。

2.2、广度优先算法

如果我们从广度优先算法来遍历这棵树的节点,那么遍历的顺序是ABCDEFGH。

广度优先遍历也叫广度优先搜索(Breadth First Search)。它的遍历规则:

1)先访问完当前顶点的所有邻接点。(应该看得出广度的意思)

2)先访问顶点的邻接点先于后访问顶点的邻接点被访问。

从A开始遍历。

遍历分析:A有两个邻接点B和C,于是按序遍历B、C。B先于C被访问,于是B的邻接点应先于C的邻接点被访问,那就是接着访问D、E。然后在回到C,C有两个邻接点F、G。再按同样的规则访问D、E、F、G的的邻接点,只有F有一个邻接点H。广度遍历完毕,最后得出的结果为ABCDEFGH。

使用Python代码实现的伪代码如下:

广度优先算法

从代码可以知道广度优先算法是使用队列实现的。

三、总结和分析

3.1、总结

深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历、中序遍历、后序遍历(我们前面使用的是先序遍历)。具体说明如下:

先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树。

中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树。

后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。

广度优先遍历:又叫层次遍历,从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。

3.2、分析

深度优先搜素算法:不全部保留结点,占用空间少;有回溯操作(即有入栈、出栈操作),运行速度慢。

广度优先搜索算法:保留全部结点,占用空间大; 无回溯操作(即无入栈、出栈操作),运行速度快。

通常深度优先搜索法不全部保留结点,扩展完的结点从数据库中弹出删去,这样,一般在数据库中存储的结点数就是深度值,因此它占用空间较少。

所以,当搜索树的结点较多,用其它方法易产生内存溢出时,深度优先搜索不失为一种有效的求解方法。

广度优先搜索算法,一般需存储产生的所有结点,占用的存储空间要比深度优先搜索大得多,因此,程序设计中,必须考虑溢出和节省内存空间的问题。

但广度优先搜索法一般无回溯操作,即入栈和出栈的操作,所以运行速度比深度优先搜索要快些。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017.10.25 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档