爬虫扩展——深度优先与广度优先原理

青旅半醒 2023-09-29 06:23 93阅读 0赞

**目录**

前言

一. 深度优先和广度优先原理

二. python实现

总结

爬虫文章专栏

--------------------

## 前言 ##

>  我们之前已经了解过了如何利用爬虫来爬取我们想要的数据，但是仅限于爬取有限的 URL，这样严格来说并不算是爬虫，我们利用爬虫要爬取的应该是大量的数据，同时就对应着要爬取大量的 URL。

> 网站的爬取一般有两种爬取策略：深度优先和广度优先。

--------------------

## 一. 深度优先和广度优先原理 ##

*  深度优先原理：

>  一个页面可能有 100 个 URL，先选择第一个 URL 发起请求，我们将这个 URL 暂时叫做 url\_level1，然后就进入了 url\_level1 的界面。再在这个界面中选择第一个 URL，判断是否已经向这个 URL 发起过请求，如果有，就选择第二个 URL，依次类推，找到未向其发起请求的第一个 URL，然后向它发起请求，我们将这个 URL 暂时叫做 url\_level2，然后就进入了 url\_level2 的界面。再在这个界面中选择第一个 URL，判断是否已经向这个 URL 发起过请求，如果有，就选择第二个 URL，依次类推，找到未向其发起请求的第一个 URL，然后向它发起请求，我们将这个 URL 暂时叫做 url\_level3，然后就进入了 url\_level3 的界面。同理，我们一层层深入下去，直到最后一个界面中的 URL 都被发起过请求，然后就倒退回上一层，继续往下深入。如此反复，就能爬取到网站的所有 URL。

接下来我们来看一个图，再来理解下深度优先的过程是怎么样的：

![94573936c07a40ba9c21dda6f67f1a31.png][]

>  本图是一个二叉树（数据结构的相关知识，了解下就可以），我们可以简单看作是一 
> 
> 个网页的所有 URL 分布，深度优先最终得到的结果是什么呢？

>  从 A 开始，先进入 B，然后进入 D，再进入 H，发现已经到底了，然后退回 D，发现D 下的 H 已经处理过，也没有其他内容了，就退回 B，发现 B 还有 E 没有遍历，就进入 E，又到底了，就退回 B，同理，又退回到 A，进入 C，再进入 F，到底了，退回C，进入 G，发现 G 左边没有节点，就进入 I，到这里就已经完全结束了。得到的最终结果就是 A-B-D-H-E-C-F-G-I。再退回去理解一下网站爬取的深度优先策略，是不是就容易了一点。

*  广度优先原理：

>  一个页面可能有 100 个 URL，依次向这 100 个 URL 发起请求，我们将这些 URL 暂时叫做 url\_level1\_one，url\_leve1\_two.....url\_level1\_hundred 然后进入 url\_level1\_one 的页面，这个页面可能有 80 个 URL，然后依次向这 80 个URL 发起请求（先判断是否已经发起过请求，如果已发起过，就略过，不再发起请求），我们将这个 URL 暂时叫做 url\_leve2\_one\_1，url\_level2\_one\_2...url\_level2\_one\_eighty然后再进入 url\_level1\_two 的页面，这个页面可能有 60 个 URL，然后依次向这 60 个URL 发起请求（先判断是否已经发起过请求，如果已发起过，就略过，不再发起请求），我们将这个 URL 暂时叫做url\_leve2\_two\_1，url\_level2\_two\_2...url\_level2\_two\_sixty同理，我们先爬取当前页面的所有 URL，然后进入当前页面的第一个 URL，爬取这个URL 下的所有 URL，然后进入第二个 URL，爬取这个 URL 下的所有 URL，依次类推，就能获取到该网站下所有的 URL。

同样的，还是来看上面的图，再来理解下广度优先的过程是怎么样的：

![6ec9aa685aae4abaabce7be5188e0da8.png][]

>  从 A 开始，先进入 B，再进入 C，再回到 B，进入 B 下面的 D，再进入 E，再回到 C，进入 C 下面的 F，再进入 G，再回到 D，进入 D 下的 H，发现 D 下已经没有元素了，就回到 E，发现 E 下没有元素，就回到 F，同样的，F 下没有元素，就回到 G，发现 G下面左边没有节点，就进入 I，这样就已经结束了。得到的最终结果是 A-B-C-D-E-F-G-H-I。再退回去理解一下网站爬取的广度优先策略，是不是就容易了一点。

--------------------

## 二. python实现 ##

*  深度优先如何用 python 进行实现：

# 实现功能：深度优先遍历（只是作为某一个数据结构的一部分，并不能运行，只是演示原理）
    # 采用方法：递归实现（对递归有兴趣的童鞋可以去了解下，自己实现数据结构时经常用到）
    def depth_first(Root_Node):
        if Root_Node is None:
        # 递归到底的情况是：如果当前结果为 None，就直接 return
            return
        print(Root_Node.value)
        if Root_Node.Left_Node:
        # 如果当前节点有左子节点，那么就递归，将当前节点的左子节点作为参数传递进去
            return depth_first(Root_Node.Left_Node)
        if Root_Node.Right_Node:
        # 如果当前节点有右子节点，那么就递归，将当前节点的右子节点作为参数传递进去
            return depth_first(Root_Node.Right_Node)

*  广度优先如何用 python 进行实现：

def breadth_first(Root_Node):
        if Root_Node is None:
        # 递归到底的情况是：如果当前结果为 None，就直接 return
            return
        queue = []
        queue.append(Root_Node)
        # 将当前节点加入到队列中
        while queue:
        # 只要列表不为空，就一直循环
            Node = queue.pop(0)
            # 每次循环都将列表的第一个元素 pop 出去
            print(Node.value)
            if Root_Node.Left_Node:
            # 如果当前节点的左子节点存在，那么就添加到列表的尾部
                queue.append(Root_Node.Left_Node)
            if Root_Node.Right_Node:
            # 如果当前节点的右子节点存在，那么就添加到列表的尾部
                queue.append(Root_Node.Right_Node)

--------------------

## 总结 ##

本文为大家介绍网站爬取深度优先与广度优先原理，希望对大家有帮助~~

欢迎大家留言一起讨论问题~~~

--------------------

**注：本文是参考风变编程课程资料（已经授权）及部分百度资料整理所得，系博主个人整理知识的文章，如有侵权，请联系博主，感谢~**

--------------------

## **爬虫文章专栏** ##

[https://blog.csdn.net/weixin\_53919192/category\_11748211.html![icon-default.png_t_M3K6][]https://blog.csdn.net/weixin\_53919192/category\_11748211.html][https_blog.csdn.net_weixin_53919192_category_11748211.html_icon-default.png_t_M3K6_https_blog.csdn.net_weixin_53919192_category_11748211.html]

[94573936c07a40ba9c21dda6f67f1a31.png]: https://img-blog.csdnimg.cn/94573936c07a40ba9c21dda6f67f1a31.png
[6ec9aa685aae4abaabce7be5188e0da8.png]: https://img-blog.csdnimg.cn/6ec9aa685aae4abaabce7be5188e0da8.png
[icon-default.png_t_M3K6]: https://csdnimg.cn/release/blog_editor_html/release2.1.0/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=M3K6
[https_blog.csdn.net_weixin_53919192_category_11748211.html_icon-default.png_t_M3K6_https_blog.csdn.net_weixin_53919192_category_11748211.html]: https://blog.csdn.net/weixin_53919192/category_11748211.html