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