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

我们今天要学习的内容,主要是给大家普及一下深度优先算法的基本概念,详情内容如下。

学过网站设计的小伙伴们都知道网站通常都是分层进行设计的,最上层的是顶级域名,之后是子域名,子域名下又有子域名等等,同时,每个子域名可能还会拥有多个同级域名,而且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到木有咧?

--------- End ---------

原文发布于微信公众号 - Python爬虫与数据挖掘(crawler_python)

原文发表时间:2018-11-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

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

​关于M4A文件的随机访问

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

40480
来自专栏ChaMd5安全团队

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

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

1.1K120
来自专栏Python爬虫与数据挖掘

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

学过网站设计的小伙伴们都知道网站通常都是分层进行设计的,最上层的是顶级域名,之后是子域名,子域名下又有子域名等等,同时,每个子域名可能还会拥有多个同级域名,而且...

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

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

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

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

pytorch中retain_graph参数的作用

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

92140
来自专栏大数据文摘

斯坦福深度学习课程第六弹:一起来学Tensorflow part1

22450
来自专栏人工智能LeadAI

tensorflow的数据输入

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

13950
来自专栏吉浦迅科技

DAY15:阅读CUDA C runtime之纹理内存

15730
来自专栏yl 成长笔记

设计模式之策略模式

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

11030
来自专栏王小雷

R语言基础命令与安装

1. R的安装过程 1.1.首先附上清华线路的下载链接Windows版3.3.1 1.2. 选择安装路径 ? 1.3. 注意根据自己的计算机位数选择,如我的是6...

25050

扫码关注云+社区

领取腾讯云代金券