1.2.2 圖的遍歷

圖的遍歷是指從圖中的某一頂點出發，按照某種搜索算法沿著圖中的邊對圖中的所有頂點訪問一次且僅訪問一次。圖的遍歷主要有兩種算法：深度優先搜索（DFS，Depth-First-Search）和廣度優先搜索（BFS，Breadth-First-Search）。圖的遍歷是一種重要的圖檢索手段，深度優先搜索與廣度優先搜索給出了相應的算法基礎。

深度優先搜索是一個遞歸算法，有回退過程。其算法思想是：從圖中某一頂點vi開始，由vi出發，訪問它的任意一個鄰居w1；再從w1出發，訪問w1的所有鄰居中未被訪問過的頂點w2；然后再從w2出發，依次訪問，直到出現某頂點不再有鄰居未被訪問過。接著，回退一步，回退到前一次剛訪問過的頂點，看是否還有其他未被訪問過的鄰居，如果有，則訪問該鄰居，之后再從該鄰居出發，進行與前面類似的訪問；如果沒有，就再回退一步進行類似訪問。重復上述過程，直到該圖中所有頂點都被訪問過為止。以圖1-7為例，我們可以得到如下深度優先搜索序列：v1→v2→v4→v5→v3。

廣度優先搜索是一個分層的搜索過程，沒有回退過程，其算法思想是：從圖中某一頂點vi開始，由vi出發，依次訪問vi的所有未被訪問過的鄰居w1，w2，…，wn；然后再順序訪問w1，w2，…，wn的所有還未被訪問過的鄰居，如此一層層執行下去，直到圖中所有頂點都被訪問到為止。以圖1-7為例，我們可以得到如下廣度優先搜索序列：v1→v2→v3→v4→v5。