浅谈网络爬虫中深度优先算法和简单代码实现

学过网站设计的小伙伴们都知道网站通常都是分层进行设计的,最上层的是顶级域名,之后是子域名,子域名下又有子域名等等,同时,每个子域名可能还会拥有多个同级域名,而且URL之间可能还有相互链接,千姿百态,由此构成一个复杂的网络。

当一个网站的URL非常多的时候,我们务必要设计好URL,否则在后期的理解、维护或者开发过程中就会非常的混乱。理解以上的网页结构设计之后,现在正式的引入网络爬虫中的深度优先算法。

上图是一个二叉树结构,通过对这个二叉树的遍历,来类比抓取网页,加深对爬虫策略的理解。深度优先算法的主要思想是首先从顶级域名A开始,之后从中提取出两个链接B和C,待链接B抓取完成之后,下一个要抓取的链接则是D或者E,而不是说抓取完成链接B之后,立马去抓取链接C。抓取完链接D之后,发现链接D中所有的URL已经被访问过了,在这之前我们已经建立了一个被访问过的URL列表,专门用于存储被访问过的URL。当链接D完全被抓取完成之后,接下来就会去抓取链接E。待链接E爬取完成之后,不会去爬取链接C,而是会继续往下深入的去爬取链接I。原则就是链接会一步一步的往下爬,只要链接下还有子链接,且该子链接尚未被访问过,这就是深度优先算法的主要思想。深度优先算法是让爬虫一步一步往下进行抓取完成之后,再一步一步退回来,优先考虑深度。理解好深度优先算法之后,再来看上图,可以得到该二叉树呈现的爬虫抓取链接的顺序依次为:A、B、D、E、I、C、F、G、H(这里假设左边的链接先会被爬取)。实际上,我们在做网络爬虫过程中,很多时候都是在用这种算法进行实现的,其实我们常用的Scrapy爬虫框架默认也是用该算法来进行实现的。通过上面的理解,我们可以认为深度优先算法本质上是通过递归的方式来进行实现的。

下图展示的是深度优先算法的代码实现过程。

深度优先过程实际上是通过一种递归的方式来进行实现的。看上图的代码,首先定义一个函数,用于实现深度优先过程,然后传入节点参数,如果该节点非空的话,则将其打印出来,可以类比一下二叉树中的顶级点A。将节点打印完成之后,看看其是否存在左节点(链接B)和右节点(链接C),如果左节点非空的话,则将其进行返回,再次调用深度优先函数本身进行递归,得到新的左节点(链接D)和右节点(链接E),以此类推,直到所有的节点都被遍历或者达到既定的条件才会停止。右节点的实现过程亦是如此,不再赘述。

深度优先过程通过递归的方式来进行实现,当递归不断进行,没有跳出递归或者递归太深的话,很容易出现栈溢出的情况,所以在实际应用的过程中要有这个意识。

深度优先算法和广度优先算法是数据结构里边非常重要的一种算法结构,也是非常常用的一种算法,而且在面试过程中也是非常常见的一道面试题,所以建议大家都需要掌握它,下一篇文章我们将介绍广度优先算法,敬请期待。

关于网络爬虫中深度优先算法的简单介绍就到这里了,小伙伴们get到木有咧?

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏牛客网

百度云部门 C++面试

14)读套接口时候返回0,时候时候产生EAGIN。【EAGIN也不太清楚,知道又这个玩意,不知道具体的,应该直接说不知道】

17320
来自专栏杨熹的专栏

几种简单的文本数据预处理方法

本文将介绍几种简单的文本数据预处理方法,希望与大家共同学习分享。

34140
来自专栏深度学习那些事儿

pytorch中retain_graph参数的作用

在pytorch神经网络迁移的官方教程中有这样一个损失层函数(具体看这里提供0.3.0版中文链接:https://oldpan.me/archives/pyto...

97640
来自专栏落影的专栏

程序员进阶之算法练习(十四)

前言 坚持做算法练习对开发的好处是抽象能力变强,拿到一个需求能很快对其进行抽象,然后再用学过的设计模式相关知识进行整理,最后用代码实现。 最大的好处在于:对...

36370
来自专栏码匠的流水账

HashedWheelTimer算法详解

George Varghese 和 Tony Lauck 1996 年的论文:Hashed and Hierarchical Timing Wheels: da...

22310
来自专栏QQ音乐技术团队的专栏

​关于 M4A 文件的随机访问

文章介绍了 M4A 文件的大概结构,详细解读了其中的 Sample Table Box,并结合图例,详细讲解了如何使用它来完成 M4A 文件的随机访问。

47500
来自专栏yl 成长笔记

设计模式之策略模式

The strategy pattern(also known as the policy pattern) is a behavioural software...

11330
来自专栏ChaMd5安全团队

小姐姐教你做CTF逆向题:利用符号执行技术和约束求解器

0x00 前言 在CTF比赛中,逆向类题目常常以考察选手的逆向分析能力、算法分析能力角度出发,通过还原程序中的算法逻辑,从而获取flag。但是如果可以在程序执行...

1.1K120
来自专栏深度学习那些事儿

在pytorch中实现与TensorFlow类似的"same"方式padding

文章来自Oldpan博客:https://oldpan.me/archives/pytorch-same-padding-tflike

3.6K70
来自专栏人工智能LeadAI

tensorflow的数据输入

tensorflow有两种数据输入方法,比较简单的一种是使用feed_dict,这种方法在画graph的时候使用placeholder来站位,在真正run的时候...

14050

扫码关注云+社区

领取腾讯云代金券