浅析深度优先与广度优先的遍历算法（简单实践）

　　前段时间和产品人员、运营人员聊产品相关的事情，他们提出想通过搜集一些网站数据去剖析其它产品功能的数据情况以及拟定推广计划，因此去了解了爬虫相关的知识。

　　深度优先和广度优先算法在爬虫遍历页面url的算法的时侯常常用到，笔者在本文中主要与你们分享讲解这两个算法的原理。

　　

　　image

　　一、网站的url结构

　　每个网站都是有一定结构层次，在一个主域名下可能会有多个内容模块，网站的所有内容都是类似一个树状结构一层一层的，如下图：

　　

　　image

　　二、原理分析

　　我们把网站的结构理解为一颗树的结构，每一个页面就是一个节点，如图：

　　

　　image

　　▎深度优先算法

　　通过深度优先遍历下来的结果是: A-->B-->D-->H-->E-->C-->F-->G

　　深度优先算法过程简略来说是对每一个可能的分支路径深入到不能再深入为止，而且每位节点只能访问一次：

　　●首先访问根节点，然后依次从根节点的未被访问的邻接点出发，进行深度优先遍历，直至和根节点有路径相通的节点都被访问。

　　●若此潮流有节点未被访问，则从一个未被访问的节点出发，重新进行深度优先遍历，直到所有顶点均被访问过。

　　由深度优先算法的规则可知该算法具体实现使用递归实现的。

　　▎广度优先算法

　　通过广度优先遍历下来的结果是: ** A-->B-->C-->D-->E-->F-->G-->H**

　　广度优先算法是从一个节点开始，根据层次从上到下的遍历节点，在同一层中从左到右遍历节点：

　　●首先访问根节点，然后访问离根节点距离为1的顶点。假设有3个节点与根节点相邻，深度优化搜索会在访问根节点后访问这3个节点。

　　●在完成访问离根节点距离为1的节点后，将它取出并重复相同的过程。其中哪一个节点是第一个节点，这依照队列的数据结构来处理。

　　所以也把广度优化算法称为纵向次序遍历，因为它一层一层地访问节点。广度优化搜索通过队列实现。

　　三、简单实践

　　这两种算法在爬虫遍历页面时常常被用到，我用了广度优先算法做了一个简单的爬取网站所有 url 的 demo 。这个 demo 主要用到了 python3 的三个库 urllib 、BeautifulSoup 以及ss l。

　　Urllib 库拿来网页恳求、响应获取；BeautifulSoup 库拿来将html解析为对象进行处理；ssl是解决访问Https时不受信任SSL证书问题；这几个库还有其他功能，感兴趣的可以去了解它们的API：

　　●导入urllib、BeautifulSoup库

　　

import ssl

import urllib.request

from bs4 import BeautifulSoup

　　●获取网页内容

　　

#解决访问Https时不受信任SSL证书问题

context = ssl._create_unverified_context()

#使用urllib库抓取URL内容

resp=urllib.request.urlopen(link_url, context=context)

html=resp.read()

　　●解析网页内容（这边只解析提取网页上面的链接）

　　

#使用BeautifulSoup库解析网页内容

soup = BeautifulSoup(html, 'html.parser')

tags = soup.find_all('a')

for tag in tags:

child_urls.add(tag.attrs('href'))

　　●使用广度优先算法进行爬取

　　

while not queue.empty():

current_url = queue.get()

if current_url not in found_urls：

found_urls.add(current_url)

quene.put(getLinkUrls(current_url))

　　四、比较剖析

　　◆深度优先算法采用栈的形式，有回溯操作，不会保留全部节点，占用空间少，但运行速率较慢。

　　◆广度优先算法采用队列的形式，无回溯操作，保留全部节点，运行速率较快，但占用空间较多。

　　◆深度优先算法和广度优先算法的时间复杂度都是O(n2)，n为节点数。

　　

　　image

　　五、工具推荐

　　借助代码去抓取想要的数据并进行可视化剖析是最方便灵活的，但是好多产品和营运说到学代码，可能马上就舍弃了。

　　那么有没有不懂代码就可以实现抓取数据，进行可视化剖析的方式呢？以下就是我为你们推荐的三款工具：

　　优采云可以比较容易的从网页精确采集你须要的数据，内容涵括电商类、生活服务类、社交媒体类、论坛类。

　　**▎优采云采集器优点：

　　●操作简单，完全可视化图形操作，无需专业IT人员，任何会使用笔记本上网的人都可以轻松把握。

　　●采集任务手动分配到云端多台服务器同时执行，提高采集效率，可以挺短的时间内 获取成千上万条信息。

　　●模拟人的操作思维模式，可以登录，输入数据，点击链接，按钮等，还能对不同情况采取不同的采集流程。

　　●内置可扩充的OCR插口，支持解析图片中的文字，可将图片上的文字提取下来。

　　●采集任务手动运行，可以根据指定的周期手动采集，并且还支持最快一分钟一次的实时采集。

　　●内置从入门到精通所须要的视频教程，2分钟才能上手使用，另外还有文档，论坛，qq群等。

　　**▎优采云采集器缺点：

　　●它又免费版本，当时好*敏*感*词*须要付费或则积分。

　　●大量采集数据的时侯，容易出现采集不全的情况。

　　●判断语录较弱，无法进行复杂判定，也未能执行复杂逻辑。

　　

　　image

　　优采云采集器组建的比较久，经过了十几年的迭代，可以实现抓取、清洗、分析，挖掘及最终的可用数据呈现，一整套服务。

　　▎优采云采集器优点：

　　●采集原理是基于 web 结构的源代码提取，几乎适用于所有的网页，以及网页中才能见到的所有内容；

　　●支持插口和插件多种扩充延展，满足愈发多元化的使用需求，使优采云采集器真正做到全网通用。

　　●在每位功能上都做了优化设置，除了最基础的数据采集，更是融入了强悍的数据处理和数据发布功能，全面建立了对于数据借助的整个流程。

　　●优采云采集器在许多细节操作中配置多项可选形式。

　　●分布式高速采集系统，占用资源少。

　　●实时地监控采集,数据不易遗漏。

　　▎优采云采集器缺点：

　　●规则配置繁杂。

　　●比较占用显存和CPU资源，大批量采集速度不行，资源回收控制得不好。

　　●高级功能必须付费版能够使用。

　　

　　image

　　Tableau是数据可视化做的最好的平台之一，功能非常强悍。

　　▎Tableau 优点：

　　●优秀的数据可视化展示疗效，数据图表制做能力强

　　●操作简单，上手快不需要写代码，数据的导出和加载都是向导式

　　●内置美观的可视化图表，不用考虑配色，表格处理好格式即可。

　　▎Tableau 缺点：

　　●基于数据查询的工具，难以处理不规范数据，难以转化复杂模型。

　　●对输入数据类型有要求，运行上去比较慢，且只能支持PC笔记本，这也是好多Newsroom后来抛弃它的诱因。

　　●本身没有前端数据库房，宣称自己是显存BI，实际用上去对硬件要求极高，对于超千万条的数据剖析，必须借助于其他ETL工具处理好数据再进行后端剖析

　　●无法支持中国式复杂表样

　　●本地化服务差

　　●价格高昂

　　

　　image

　　由此可见，工具有很多优点，但也有局限，对于有大量数据需求以及比较复杂的需求时侯还是须要通过代码实现，建议感兴趣的产品和营运可以稍稍了解下 python 。

　　

　　image

　　以上，就是我对深度优先与广度优先的遍历算法的个人理解以及部份推荐的三个工具，大数据时代的到来，对数据爬取的需求越来越大，让我们一起学习上去。