淺談網(wǎng)絡(luò )爬蟲(chóng)中深度優(yōu)先算法和簡(jiǎn)單代碼實(shí)現

　　點(diǎn)擊上方“程序人生”，選擇“置頂公眾號”

　　第一時(shí)間關(guān)注程序猿（媛）身邊的故事

　　作者

　　Python進(jìn)階者

　　已獲原作者授權，如需轉載，請聯(lián)系原作者。

　　我們今天要學(xué)習的內容，主要是給大家普及一下深度優(yōu)先算法的基本概念，詳情內容如下。

　　學(xué)過(guò)網(wǎng)站設計的小伙伴們都知道網(wǎng)站通常都是分層進(jìn)行設計的，最上層的是頂級域名，之后是子域名，子域名下又有子域名等等，同時(shí)，每個(gè)子域名可能還會(huì )擁有多個(gè)同級域名，而且URL之間可能還有相互鏈接，千姿百態(tài)，由此構成一個(gè)復雜的網(wǎng)絡(luò )。

　　當一個(gè)網(wǎng)站的URL非常多的時(shí)候，我們務(wù)必要設計好URL，否則在后期的理解、維護或者開(kāi)發(fā)過(guò)程中就會(huì )非常的混亂。理解以上的網(wǎng)頁(yè)結構設計之后，現在正式的引入網(wǎng)絡(luò )爬蟲(chóng)中的深度優(yōu)先算法。

　　上圖是一個(gè)二叉樹(shù)結構，通過(guò)對這個(gè)二叉樹(shù)的遍歷，來(lái)類(lèi)比抓取網(wǎng)頁(yè)，加深對爬蟲(chóng)策略的理解。深度優(yōu)先算法的主要思想是首先從頂級域名A開(kāi)始，之后從中提取出兩個(gè)鏈接B和C，待鏈接B抓取完成之后，下一個(gè)要抓取的鏈接則是D或者E，而不是說(shuō)抓取完成鏈接B之后，立馬去抓取鏈接C。抓取完鏈接D之后，發(fā)現鏈接D中所有的URL已經(jīng)被訪(fǎng)問(wèn)過(guò)了，在這之前我們已經(jīng)建立了一個(gè)被訪(fǎng)問(wèn)過(guò)的URL列表，專(zhuān)門(mén)用于存儲被訪(fǎng)問(wèn)過(guò)的URL。當鏈接D完全被抓取完成之后，接下來(lái)就會(huì )去抓取鏈接E。待鏈接E爬取完成之后，不會(huì )去爬取鏈接C，而是會(huì )繼續往下深入的去爬取鏈接I。原則就是鏈接會(huì )一步一步的往下爬，只要鏈接下還有子鏈接，且該子鏈接尚未被訪(fǎng)問(wèn)過(guò)，這就是深度優(yōu)先算法的主要思想。深度優(yōu)先算法是讓爬蟲(chóng)一步一步往下進(jìn)行抓取完成之后，再一步一步退回來(lái)，優(yōu)先考慮深度。理解好深度優(yōu)先算法之后，再來(lái)看上圖，可以得到該二叉樹(shù)呈現的爬蟲(chóng)抓取鏈接的順序依次為：A、B、D、E、I、C、F、G、H（這里假設左邊的鏈接先會(huì )被爬?。?。實(shí)際上，我們在做網(wǎng)絡(luò )爬蟲(chóng)過(guò)程中，很多時(shí)候都是在用這種算法進(jìn)行實(shí)現的，其實(shí)我們常用的Scrapy爬蟲(chóng)框架默認也是用該算法來(lái)進(jìn)行實(shí)現的。通過(guò)上面的理解，我們可以認為深度優(yōu)先算法本質(zhì)上是通過(guò)遞歸的方式來(lái)進(jìn)行實(shí)現的。

　　下圖展示的是深度優(yōu)先算法的代碼實(shí)現過(guò)程。

　　深度優(yōu)先過(guò)程實(shí)際上是通過(guò)一種遞歸的方式來(lái)進(jìn)行實(shí)現的?？瓷蠄D的代碼，首先定義一個(gè)函數，用于實(shí)現深度優(yōu)先過(guò)程，然后傳入節點(diǎn)參數，如果該節點(diǎn)非空的話(huà)，則將其打印出來(lái)，可以類(lèi)比一下二叉樹(shù)中的頂級點(diǎn)A。將節點(diǎn)打印完成之后，看看其是否存在左節點(diǎn)（鏈接B）和右節點(diǎn)（鏈接C），如果左節點(diǎn)非空的話(huà)，則將其進(jìn)行返回，再次調用深度優(yōu)先函數本身進(jìn)行遞歸，得到新的左節點(diǎn)（鏈接D）和右節點(diǎn)（鏈接E），以此類(lèi)推，直到所有的節點(diǎn)都被遍歷或者達到既定的條件才會(huì )停止。右節點(diǎn)的實(shí)現過(guò)程亦是如此，不再贅述。

　　深度優(yōu)先過(guò)程通過(guò)遞歸的方式來(lái)進(jìn)行實(shí)現，當遞歸不斷進(jìn)行，沒(méi)有跳出遞歸或者遞歸太深的話(huà)，很容易出現棧溢出的情況，所以在實(shí)際應用的過(guò)程中要有這個(gè)意識。

　　深度優(yōu)先算法和廣度優(yōu)先算法是數據結構里邊非常重要的一種算法結構，也是非常常用的一種算法，而且在面試過(guò)程中也是非常常見(jiàn)的一道面試題，所以建議大家都需要掌握它，下一篇文章我們將介紹廣度優(yōu)先算法，敬請期待。

　　關(guān)于網(wǎng)絡(luò )爬蟲(chóng)中深度優(yōu)先算法的簡(jiǎn)單介紹就到這里了，小伙伴們get到木有咧？

　　- The End -

　　「若你有原創(chuàng )文章想與大家分享，歡迎投稿?！?/p>

　　加編輯微信ID，備注#投稿#：

　　程序 丨 druidlost

　　小七 丨 duoshangshuang