寬度優先遍歷

就是以離初狀態的狀態距離為序進行遍歷。

維護一個佇列，首先將初狀態加入佇列中，標記該狀態已搜尋，然後：

1）：取出隊首元素，將它所有可產生的未標記後繼狀態加入佇列，並將其標記為已搜尋；

2）：當佇列未空時重複1)；

具體題目加具體處理即可。

二叉樹的寬度優先遍歷

按層遍歷

如右圖：ABCDEF

圖的優先遍歷

圖的寬度優先遍歷需要一個佇列作為保存當前節點的子節點的數據結構。具體的算法如下所示：

(1)頂點V入佇列。

(2)當佇列非空時繼續執行，否則算法為空。

(3)出佇列，獲得隊頭節點V，訪問頂點V並標記V已經被訪問。

(4)查找頂點V的第一個鄰接頂點col。

(5)若V的鄰接頂點col未被訪問過，則col進佇列。

(6)繼續查找V的其他鄰接頂點col，轉到步驟(5)，若V的所有鄰接頂點都已經被訪問過，則轉到步驟(2)。

下面，我們以圖示的方式介紹寬度優先遍歷的過程，如圖1.3所示。

圖1.3 寬度優先遍歷過程

選擇A作為種子節點，則寬度優先遍歷的過程，如表1.2所示。

表1.2 寬度優先遍歷過程

在表1.2所示的遍歷過程中，出佇列的節點順序既是圖的寬度優先遍歷的訪問順序。由此可以看出，圖1.3所示的寬度優先遍歷的訪問順序為

A->B->C->D->E->F->H->G->I

相關詞條