学过网站设计的小伙伴们:二叉树结构设计
优采云 发布时间: 2021-06-07 04:24学过网站设计的小伙伴们:二叉树结构设计
研究过网站设计的人都知道网站通常是分层设计的。顶层是顶级域名,后面是子域名,子域名下面还有子域名等等,每个子域也可能有多个同级域名,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),以此类推,不会停止直到遍历完所有节点或达到既定条件。右节点的实现过程也一样,不再赘述。
深度优先过程以递归方式实现。当递归继续而不跳出递归或递归过深时,容易发生栈溢出,实际应用过程中要注意这一点。
深度优先算法和广度优先算法是数据结构中非常重要的算法结构,也是非常常用的算法,也是面试过程中非常常见的面试题,所以推荐大家需要掌握,下一篇文章我们将介绍广度优先算法,敬请期待。
对网络爬虫中深度优先算法的简单介绍到此结束。你们做对了吗?