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

目录

前言 

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

二. 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。

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

         本图是一个二叉树（数据结构的相关知识，了解下就可以），我们可以简单看作是一

个网页的所有 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。 

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

        从 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.htmlhttps://blog.csdn.net/weixin_53919192/category_11748211.html