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

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

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

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

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

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

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

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

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