前段時(shí)間和產(chǎn)品人員徊哑、運(yùn)營人員聊產(chǎn)品相關(guān)的事情，他們提出想通過收集一些網(wǎng)站數(shù)據(jù)去分析其它產(chǎn)品功能的數(shù)據(jù)情況以及制定推廣計(jì)劃聪富，因此去了解了爬蟲相關(guān)的知識莺丑。
深度優(yōu)先和廣度優(yōu)先算法在爬蟲遍歷頁面url的算法的時(shí)候經(jīng)常用到，筆者在本文中主要與大家分享講解這兩個(gè)算法的原理墩蔓。
一梢莽、網(wǎng)站的url結(jié)構(gòu)
每個(gè)網(wǎng)站都是有一定結(jié)構(gòu)層次，在一個(gè)主域名下可能會有多個(gè)內(nèi)容模塊奸披，網(wǎng)站的所有內(nèi)容都是類似一個(gè)樹形結(jié)構(gòu)一層一層的昏名，如下圖：
二、原理剖析
我們把網(wǎng)站的結(jié)構(gòu)理解為一顆樹的結(jié)構(gòu)源内，每一個(gè)頁面就是一個(gè)節(jié)點(diǎn)葡粒，如圖：
▎深度優(yōu)先算法
通過深度優(yōu)先遍歷出來的結(jié)果是: A-->B-->D-->H-->E-->C-->F-->G
深度優(yōu)先算法過程簡要來說是對每一個(gè)可能的分支路徑深入到不能再深入為止份殿，而且每個(gè)節(jié)點(diǎn)只能訪問一次：
●首先訪問根節(jié)點(diǎn)膜钓，然后依次從根節(jié)點(diǎn)的未被訪問的鄰接點(diǎn)出發(fā)，進(jìn)行深度優(yōu)先遍歷卿嘲，直至和根節(jié)點(diǎn)有路徑相通的節(jié)點(diǎn)都被訪問颂斜。
●若此時(shí)尚有節(jié)點(diǎn)未被訪問，則從一個(gè)未被訪問的節(jié)點(diǎn)出發(fā)拾枣，重新進(jìn)行深度優(yōu)先遍歷沃疮，直到所有頂點(diǎn)均被訪問過盒让。
由深度優(yōu)先算法的規(guī)則可知該算法具體實(shí)現(xiàn)使用遞歸實(shí)現(xiàn)的。
▎廣度優(yōu)先算法
通過廣度優(yōu)先遍歷出來的結(jié)果是: ** A-->B-->C-->D-->E-->F-->G-->H**
廣度優(yōu)先算法是從一個(gè)節(jié)點(diǎn)開始司蔬，根據(jù)層次從上到下的遍歷節(jié)點(diǎn)邑茄，在同一層中從左到右遍歷節(jié)點(diǎn)：
●首先訪問根節(jié)點(diǎn)，然后訪問距根節(jié)點(diǎn)距離為1的頂點(diǎn)俊啼。假設(shè)有3個(gè)節(jié)點(diǎn)與根節(jié)點(diǎn)相鄰肺缕，深度優(yōu)化搜索會在訪問根節(jié)點(diǎn)后訪問這3個(gè)節(jié)點(diǎn)。
●在完成訪問距根節(jié)點(diǎn)距離為1的節(jié)點(diǎn)后授帕，將它取出并重復(fù)相同的過程同木。其中哪一個(gè)節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn)，這根據(jù)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)來處理跛十。
所以也把廣度優(yōu)化算法稱為橫向順序遍歷彤路，因?yàn)樗粚右粚拥卦L問節(jié)點(diǎn)。廣度優(yōu)化搜索通過隊(duì)列實(shí)現(xiàn)芥映。
三洲尊、簡單實(shí)踐
這兩種算法在爬蟲遍歷頁面時(shí)經(jīng)常被用到，我用了廣度優(yōu)先算法做了一個(gè)簡單的爬取網(wǎng)站所有 url 的 demo 奈偏。這個(gè) demo 主要用到了 python3 的三個(gè)庫 urllib 颊郎、BeautifulSoup 以及ss l。
Urllib 庫用來網(wǎng)頁請求霎苗、響應(yīng)獲饶房浴；BeautifulSoup 庫用來將html解析為對象進(jìn)行處理唁盏；ssl是解決訪問Https時(shí)不受信任SSL證書問題内狸；這幾個(gè)庫還有其他功能，感興趣的可以去了解它們的API：
●導(dǎo)入urllib厘擂、BeautifulSoup庫
import ssl
import urllib.request
from bs4 import BeautifulSoup
●獲取網(wǎng)頁內(nèi)容
#解決訪問Https時(shí)不受信任SSL證書問題
context = ssl._create_unverified_context()
#使用urllib庫抓取URL內(nèi)容
resp=urllib.request.urlopen(link_url, context=context)
html=resp.read()
●解析網(wǎng)頁內(nèi)容（這邊只解析提取網(wǎng)頁里面的鏈接）
#使用BeautifulSoup庫解析網(wǎng)頁內(nèi)容
soup = BeautifulSoup(html, 'html.parser')
tags = soup.find_all('a')
for tag in tags:
child_urls.add(tag.attrs('href'))
●使用廣度優(yōu)先算法進(jìn)行爬取
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))
四昆淡、比較分析
◆深度優(yōu)先算法采用棧的方式，有回溯操作刽严，不會保留全部節(jié)點(diǎn)昂灵，占用空間少，但運(yùn)行速度較慢舞萄。
◆廣度優(yōu)先算法采用隊(duì)列的方式眨补，無回溯操作，保留全部節(jié)點(diǎn)倒脓，運(yùn)行速度較快撑螺，但占用空間較多。
◆深度優(yōu)先算法和廣度優(yōu)先算法的時(shí)間復(fù)雜度都是O(n2)崎弃，n為節(jié)點(diǎn)數(shù)甘晤。
五含潘、工具推薦
借助代碼去抓取想要的數(shù)據(jù)并進(jìn)行可視化分析是最方便靈活的，但是很多產(chǎn)品和運(yùn)營說到學(xué)代碼线婚，可能馬上就放棄了遏弱。
那么有沒有不懂代碼就可以實(shí)現(xiàn)抓取數(shù)據(jù)，進(jìn)行可視化分析的方法呢塞弊？以下就是我為大家推薦的三款工具：
- NO.1 八爪魚采集器
八爪魚可以比較容易的從網(wǎng)頁精確采集你需要的數(shù)據(jù)腾窝，內(nèi)容涵蓋電商類、生活服務(wù)類居砖、社交媒體類虹脯、論壇類。
**▎八爪魚采集器優(yōu)點(diǎn)：
●操作簡單奏候，完全可視化圖形操作循集，無需專業(yè)IT人員，任何會使用電腦上網(wǎng)的人都可以輕松掌握蔗草。
●采集任務(wù)自動(dòng)分配到云端多臺服務(wù)器同時(shí)執(zhí)行咒彤，提高采集效率，可以很短的時(shí)間內(nèi) 獲取成千上萬條信息咒精。
●模擬人的操作思維模式镶柱，可以登陸，輸入數(shù)據(jù)模叙，點(diǎn)擊鏈接歇拆，按鈕等，還能對不同情況采取不同的采集流程范咨。
●內(nèi)置可擴(kuò)展的OCR接口故觅，支持解析圖片中的文字，可將圖片上的文字提取出來渠啊。
●采集任務(wù)自動(dòng)運(yùn)行输吏，可以按照指定的周期自動(dòng)采集，并且還支持最快一分鐘一次的實(shí)時(shí)采集替蛉。
●內(nèi)置從入門到精通所需要的視頻教程贯溅，2分鐘就能上手使用，另外還有文檔躲查，論壇它浅，qq群等。
**▎八爪魚采集器缺點(diǎn)：
●它又免費(fèi)版本熙含，當(dāng)時(shí)很多功能需要付費(fèi)或者積分罚缕。
●大量采集數(shù)據(jù)的時(shí)候，容易出現(xiàn)采集不全的情況怎静。
●判斷語錄較弱邮弹，無法進(jìn)行復(fù)雜判斷，也無法執(zhí)行復(fù)雜邏輯蚓聘。
- NO.2 火車采集器 -
火車采集器成立的比較久腌乡，經(jīng)過了十幾年的迭代，可以實(shí)現(xiàn)抓取夜牡、清洗与纽、分析，挖掘及最終的可用數(shù)據(jù)呈現(xiàn)塘装，一整套服務(wù)急迂。
▎火車采集器優(yōu)點(diǎn)：
●采集原理是基于 web 結(jié)構(gòu)的源代碼提取，幾乎適用于所有的網(wǎng)頁蹦肴，以及網(wǎng)頁中能夠看到的所有內(nèi)容僚碎；
●支持接口和插件多種擴(kuò)展延伸，滿足更加多樣化的使用需求阴幌，使火車采集器真正做到全網(wǎng)通用勺阐。
●在每個(gè)功能上都做了優(yōu)化設(shè)置，除了最基礎(chǔ)的數(shù)據(jù)采集矛双，更是融入了強(qiáng)大的數(shù)據(jù)處理和數(shù)據(jù)發(fā)布功能渊抽，全面完善了對于數(shù)據(jù)利用的整個(gè)流程。
●火車采集器在許多細(xì)節(jié)操作中配置多項(xiàng)可選方式议忽。
●分布式高速采集系統(tǒng)懒闷，占用資源少。
●實(shí)時(shí)地監(jiān)控采集,數(shù)據(jù)不易遺漏栈幸。
▎火車采集器缺點(diǎn)：
●規(guī)則配置煩瑣毛雇。
●比較占用內(nèi)存和CPU資源，大批量采集速度不行侦镇，資源回收控制得不好灵疮。
●高級功能必須付費(fèi)版才能使用。
- NO.3 Tableau -
Tableau是數(shù)據(jù)可視化做的最好的平臺之一壳繁，功能十分強(qiáng)大震捣。
▎Tableau 優(yōu)點(diǎn)：
●優(yōu)秀的數(shù)據(jù)可視化展示效果，數(shù)據(jù)圖表制作能力強(qiáng)
●操作簡單闹炉，上手快不需要寫代碼蒿赢，數(shù)據(jù)的導(dǎo)入和加載都是向?qū)?/p>
●內(nèi)置美觀的可視化圖表，不用考慮配色渣触，表格處理好格式即可羡棵。
▎Tableau 缺點(diǎn)：
●基于數(shù)據(jù)查詢的工具，難以處理不規(guī)范數(shù)據(jù)嗅钻，難以轉(zhuǎn)化復(fù)雜模型皂冰。
●對輸入數(shù)據(jù)類型有要求店展，運(yùn)行起來比較慢，且只能支持PC電腦秃流，這也是很多Newsroom后來拋棄它的原因赂蕴。
●本身沒有后端數(shù)據(jù)倉庫，宣稱自己是內(nèi)存BI舶胀，實(shí)際用起來對硬件要求極高概说，對于超千萬條的數(shù)據(jù)分析，必須借助于其他ETL工具處理好數(shù)據(jù)再進(jìn)行前端分析
●無法支持中國式復(fù)雜表樣
●本地化服務(wù)差
●價(jià)格昂貴
由此可見嚣伐，工具有很多優(yōu)點(diǎn)糖赔，但也有局限，對于有大量數(shù)據(jù)需求以及比較復(fù)雜的需求時(shí)候還是需要通過代碼實(shí)現(xiàn)轩端，建議感興趣的產(chǎn)品和運(yùn)營可以稍微了解下 python 放典。
以上，就是我對深度優(yōu)先與廣度優(yōu)先的遍歷算法的個(gè)人理解以及部分推薦的三個(gè)工具船万，大數(shù)據(jù)時(shí)代的到來刻撒，對數(shù)據(jù)爬取的需求越來越大，讓我們一起學(xué)習(xí)起來耿导。
