深度優(yōu)先和廣度優(yōu)先算法在爬取一個整站上經(jīng)常用到，本課程主要講解這兩個算法的原理以及使用過程。
一、網(wǎng)站的樹結(jié)構
1.1、一個網(wǎng)站的url結(jié)構圖
以知乎為例，知乎目前有發(fā)現(xiàn)、話題、Live、書店、圓桌、專欄主要的6個tab頁。每個網(wǎng)站的url都是有一定的層次，如下圖：發(fā)現(xiàn)explore、話題topic、Live lives、書店pub、圓桌roundtable、專欄zhuanlan都是在主域名zhihu的下一級，而具體的Live在zhuhu.com/lives/770340328338104320，內(nèi)容又在話題之下zhihu/question/67006058/answer/250037350，網(wǎng)站的所有內(nèi)容都一層一層的類似一個樹形結(jié)構。
1.2、網(wǎng)站url鏈接的結(jié)構圖
當然，如果我們要做爬取整個網(wǎng)站的url時，我們必須要知道每個網(wǎng)站的url鏈接一般情況下都是存在環(huán)路的，也就是在下一級頁面存在上一級頁面的url鏈接，這樣形成一個環(huán)路。當遇到這個情況時我們需要做url去重，一般的處理方式是把已經(jīng)爬過的url放到一個list，每次爬取url的時候都去這個list查看下是否已經(jīng)爬過，爬過的就跳過。這塊url去重我下次再詳細介紹。
二、深度優(yōu)先和廣度優(yōu)先算法原理介紹（以二叉樹為例）
為了更加容易理解深度優(yōu)先和廣度優(yōu)先算法的原理，我們把一個網(wǎng)站的Tab理解成一顆樹的節(jié)點，如下圖：
2.1、深度優(yōu)先算法
如果我們從深度優(yōu)先算法來遍歷這棵樹的節(jié)點，那么遍歷的順序是ABDECFHG。
深度優(yōu)先遍歷也叫深度優(yōu)先搜索(Depth First Search)。它的遍歷規(guī)則：不斷地沿著頂點的深度方向遍歷。頂點的深度方向是指它的鄰接點方向。
從A開始遍歷。
遍歷分析：A有兩個鄰接點B和C，選擇下標小的B遍歷。接著從B開始深度遍歷，B有兩個鄰接點D和E，選擇下標小的D開始深度遍歷，D下面沒有鄰接點，那么回溯到B深度往右遍歷到E，E下面沒有鄰接點。至此，遍歷得到的值為ABDE。EDB下的節(jié)點都遍歷完之后就會從C開始深度遍歷，同理遍歷得出的值為CFHG。那么最后得出的結(jié)果為ABDECFHG。
使用Python代碼實現(xiàn)的偽代碼如下：
從代碼可以知道深度優(yōu)先算法是使用遞歸實現(xiàn)的。
2.2、廣度優(yōu)先算法
如果我們從廣度優(yōu)先算法來遍歷這棵樹的節(jié)點，那么遍歷的順序是ABCDEFGH。
廣度優(yōu)先遍歷也叫廣度優(yōu)先搜索(Breadth First Search)。它的遍歷規(guī)則：
1）先訪問完當前頂點的所有鄰接點。(應該看得出廣度的意思)
2）先訪問頂點的鄰接點先于后訪問頂點的鄰接點被訪問。
從A開始遍歷。
遍歷分析：A有兩個鄰接點B和C，于是按序遍歷B、C。B先于C被訪問，于是B的鄰接點應先于C的鄰接點被訪問，那就是接著訪問D、E。然后在回到C，C有兩個鄰接點F、G。再按同樣的規(guī)則訪問D、E、F、G的的鄰接點，只有F有一個鄰接點H。廣度遍歷完畢，最后得出的結(jié)果為ABCDEFGH。
使用Python代碼實現(xiàn)的偽代碼如下：
從代碼可以知道廣度優(yōu)先算法是使用隊列實現(xiàn)的。
三、總結(jié)和分析
3.1、總結(jié)
深度優(yōu)先遍歷：對每一個可能的分支路徑深入到不能再深入為止，而且每個結(jié)點只能訪問一次。要特別注意的是，二叉樹的深度優(yōu)先遍歷比較特殊，可以細分為先序遍歷、中序遍歷、后序遍歷（我們前面使用的是先序遍歷）。具體說明如下：
先序遍歷：對任一子樹，先訪問根，然后遍歷其左子樹，最后遍歷其右子樹。
中序遍歷：對任一子樹，先遍歷其左子樹，然后訪問根，最后遍歷其右子樹。
后序遍歷：對任一子樹，先遍歷其左子樹，然后遍歷其右子樹，最后訪問根。
廣度優(yōu)先遍歷：又叫層次遍歷，從上往下對每一層依次訪問，在每一層中，從左往右（也可以從右往左）訪問結(jié)點，訪問完一層就進入下一層，直到?jīng)]有結(jié)點可以訪問為止。
3.2、分析
深度優(yōu)先搜素算法：不全部保留結(jié)點，占用空間少；有回溯操作(即有入棧、出棧操作)，運行速度慢。
廣度優(yōu)先搜索算法：保留全部結(jié)點，占用空間大； 無回溯操作(即無入棧、出棧操作)，運行速度快。
通常深度優(yōu)先搜索法不全部保留結(jié)點，擴展完的結(jié)點從數(shù)據(jù)庫中彈出刪去，這樣，一般在數(shù)據(jù)庫中存儲的結(jié)點數(shù)就是深度值，因此它占用空間較少。
所以，當搜索樹的結(jié)點較多，用其它方法易產(chǎn)生內(nèi)存溢出時，深度優(yōu)先搜索不失為一種有效的求解方法。
廣度優(yōu)先搜索算法，一般需存儲產(chǎn)生的所有結(jié)點，占用的存儲空間要比深度優(yōu)先搜索大得多，因此，程序設計中，必須考慮溢出和節(jié)省內(nèi)存空間的問題。
但廣度優(yōu)先搜索法一般無回溯操作，即入棧和出棧的操作，所以運行速度比深度優(yōu)先搜索要快些。
