廣度優先演算法與深度優先演算法比一比
先前我們曾經提過,圖論(Graph theory)的起源,最早來自於柯尼斯堡的七橋問題。而解決該七橋問題的尤拉(Leonhard Euler,1707~1783),則被認為是圖論的創始人。其實,透過拓撲學的圖論,可以協助解決許多問題,其中像是如何進行網路搜尋或爬蟲,就是圖論的延伸。
1993年,魔賽克網路瀏覽器(Mosaic web-browser)剛剛面世。幾個月後,麻省理工學院學生馬修·葛雷(Matthew Gray)也寫出了一支稱為World Wide Web Wanderer的世界上第一個網路機器人爬蟲程式,該程式能以系統性的方式,遊歷各Web網站並蒐集站點資料。
從現在的觀點來看,當年的World Wide Web上的資料,可能只是目前網路資料的九牛一毛,但是當年的電腦效率,有了搜尋程式已讓網路使用者省力很多。但您有沒有想過,如何搜尋才是最有效或者是最省力的方式?這就牽涉到進行網路爬蟲時,兩種常用的演算法:廣度優先搜尋(Breadth-First Search,BFS)與深度優先搜尋(Depth-First-Search,DFS)。
所謂的廣度優先,就是從圖的某一節點開始走起,然後逐一走過此一節點相鄰且所有未走過的節點,再由走訪過的節點,接續進行「先廣後深」的搜索方式。 換句話說,利用樹狀系統,就即把同一層級的節點走過一次,然後再繼續向下一層級搜尋,直到找到所要的目標,或者已尋遍所有的節點。不曉得,各位有沒有發現,這種概念跟七橋問題幾乎一模一樣。
我們再以下面圖1顯示的網路圖來說明。「廣度優先」搜尋會先搜尋第一層與A相連的點(即ABCD),再搜尋第一層相連的點EFGH,以此類推,所以搜尋順序為A、B、C、D、E、F、G、H、I、J、K、L。
至於深度優先搜尋(Depth-First-Search,DFS)則是深入一個節點後,再單刀直入,深入下一個節點。所以搜尋順序為A、B、C─E、F─I─J、D─G、H─K─L。
不過,如此一來,網友一定會問,這兩種演算法,到底哪一個比較好,或是適用的情境為何?
一般來說,一個網站最重要的應該是它的門面(網站首頁),以及最接近首頁的那幾層網頁。從這樣的觀點來看,在時間、資源有限的情況下,要爬取到最重要資料的網頁,「廣度優先搜尋(BFS)」應該是優於「深度優先搜尋(DFS)」。
不過,使用DFS的好處是,可以增加爬蟲的效率,畢竟一直換網站搜尋或下載,背後有其時間成本。採用廣度優先搜尋時,如果找不到所要的資料時,爬蟲程式會先到一個網站去,然後再到另一個網站,之後再回到原有網站下載。而這樣換來換去,也就犧牲了效率。
所以,後來又出現了最佳優先搜尋(Best-First Search)方法,背後則是透過一個「優先排序系統」,來決定應該下載哪個網頁。
了解這些原理之後,對於像我們這類網路搜尋的重度使用者來說,都會對這些搜尋程式心存感激,畢竟如果沒有這些程式,為了找到某些特定資料,可能找到海枯石爛都找不到。
作者 : 羅凱揚(台科大企管系博士)、蘇宇暉(台科大管研所博士候選人)