廣度優先演算法與深度優先演算法比一比
先前我們曾經提過，圖論（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）方法，背後則是透過一個「優先排序系統」，來決定應該下載哪個網頁。
了解這些原理之後，對於像我們這類網路搜尋的重度使用者來說，都會對這些搜尋程式心存感激，畢竟如果沒有這些程式，為了找到某些特定資料，可能找到海枯石爛都找不到。
作者 : 羅凱揚（台科大企管系博士）、蘇宇暉（台科大管研所博士候選人）
