算法導論--廣度優先搜索和深度優先搜索，導論深度優先搜索

算法導論--廣度優先搜索和深度優先搜索，導論深度優先搜索

廣度優先搜索

在給定圖G=(V,E)和一個特定的源頂點s的情況下，廣度優先搜索系統地探索G中的邊，以期“發現”可從s 到達的所有頂點，並計算s 到所有這些可達頂點之間的距離（即最少的邊數）。該搜索算法同時還能生成一棵根為s、且包括所有s 的可達頂點的廣度優先樹。對從s 可達的任意頂點v，廣度優先樹中從s 到v 的路徑對應於圖G中從s 到v 的一條最短路徑，即包含最少邊數的路徑。該算法對有向圖和無向圖同樣適用。

 具體算法詳情見 算法—12.廣度優先搜索

算法分析：

現在分析一下該算法在輸入圖G=(V,E)上的運行時間。此處采用聚集分析技術，在初始化後，再沒有任何頂點被置為白色。因此，第13行中的測試保證了每個頂點至多只進入隊列一次，因而至多只從隊列中出來一次。入隊和出隊操作需要O(1)的時間，因此隊列操作所需的全部時間為O(V)。因為只有當每個頂點將出隊時，才會掃描其鄰接表，因而每個頂點的鄰接表至多被掃描一次。由於所有鄰接表的長度和為O(E)，故掃描所有鄰接表所花費的全部時間為O(E)。初始化操作的開銷為O(V)，於是，過程BFS的總運行時間為O(V+E)。由此可見，廣度優先搜索的運行時間是圖G的鄰接表大小的一個線性函數。

深度優先搜索

正如“深度優先搜索”這一名稱所暗示的那樣，這種搜索算法所遵循的搜索策略是盡可能“深”地搜索一個圖。在深度優先搜索中，對於最新發現的頂點，如果它還有以此為起點而未探測到的邊，就沿此邊繼續探測下去。當頂點v的所有邊都已被探尋過後，搜索將回溯到發現頂點v 有起始點的那些邊。這一過程一直進行到已發現從源頂點可達的所有頂點時為止。如果還存在未被發現的頂點，則選擇其中一個作為源頂點，並重復以上過程。整個過程反復進行，直到所有的頂點都已被發現時為止。

算法—11.深度優先搜索

算法分析：

DFS中第1~3行和第5~7行中的循環占用的時間為O(V)，這不包括調用DFS-VISIT的時間。就像我們在處理廣度優先搜索時一樣，采用聚集分析。對於每個頂點vΕV，過程DFS-VISIT僅被調用一次，因為只有對白色頂點才會調用該過程，且該過程所做的第一件事就是將頂點置為灰色。在DFS-VISIT(v)的一次執行過程中，第4~7行中的循環被執行了| Adj[v] |次。因為有

故執行過程DFS-VISIT中第4~7行的總代價為O(E)。因此，DFS的運行時間為O(V+E)。