一、深度優(yōu)先搜索 DFS
1、深度優(yōu)先搜索和廣度優(yōu)先搜索
圖 的 遍歷 就是 對 圖 中的 結(jié)點 進(jìn)行遍歷 , 遍歷 結(jié)點 有如下兩種策略 :
- 深度優(yōu)先搜索 DFS
- 廣度優(yōu)先搜索 BFS
2、深度優(yōu)先搜索基本思想
" 深度優(yōu)先搜索 " 英文名稱是 Depth First Search , 簡稱 DFS ;
DFS 基本思想 :
- 訪問第一個鄰接結(jié)點 : 從 起始點 出發(fā) , 該 起始點 可能有 若干 鄰接結(jié)點 , 訪問 第一個 鄰接結(jié)點 , 然后 再訪問 第一個 鄰接結(jié)點 的 第一個鄰接結(jié)點 , 每次都訪問 當(dāng)前結(jié)點 的 第一個鄰接結(jié)點 ;
- 訪問策略 : 優(yōu)先 向 縱向遍歷 , 不是 對 當(dāng)前結(jié)點 的所有 鄰接結(jié)點 進(jìn)行 橫向遍歷 ;
- 遞歸過程 : 上述 DFS , 每次訪問 起始點 的 第一個鄰接結(jié)點 后 , 又將 該 第一個鄰接結(jié)點 作為 新的起始點 繼續(xù)向下訪問 , 該過程是一個遞歸過程 ;
3、深度優(yōu)先搜索算法步驟
深度優(yōu)先搜索算法步驟 :
- ① 訪問初始結(jié)點 : 訪問 初始結(jié)點 v , 并將該 初始結(jié)點 v 標(biāo)記為 " 已訪問 " ;
- ② 查找鄰接節(jié)點 : 查找 初始結(jié)點 v 的 第一個 鄰接節(jié)點 w ;
-
③ 鄰接節(jié)點是否存在 :
- 如果 w 結(jié)點存在 , 執(zhí)行 ④ 操作 判斷該 結(jié)點 是否被訪問 ;
- 如果 w 結(jié)點 不存在 , 回到 ① 查找 初始結(jié)點 v 的下一個 鄰接節(jié)點 ;
-
④ 鄰接節(jié)點是否被訪問 :
- 如果 w 結(jié)點存在 并且 沒有被訪問 , 那么 對 w 結(jié)點 進(jìn)行 深度優(yōu)先遍歷 , 將 w 結(jié)點 作為 新的 初始結(jié)點 v , 從 ① 步驟開始執(zhí)行 ;
- 如果 w 結(jié)點存在 但是 被訪問了 , 那么 查找 w 結(jié)點的 下一個 鄰接節(jié)點 , 轉(zhuǎn)到步驟 ③ 執(zhí)行 ;
二、深度優(yōu)先搜索示例 ( 理論 )
以下圖為例 , 說明 DFS 搜索步驟 ; 初始結(jié)點 A ;
初始結(jié)點 為 A , 開始進(jìn)行 DFS :
1、第一輪遞歸
訪問 初始結(jié)點 A , 并將該 初始結(jié)點 A 標(biāo)記為 " 已訪問 " ;
查找 初始結(jié)點 A 的 第一個 鄰接節(jié)點 B ;
- 鄰接結(jié)點選擇 : 這里的 第一個鄰接節(jié)點 選擇 , 是在內(nèi)存數(shù)據(jù) 鄰接表 中排列在首位 0 索引的節(jié)點 , 或者 與 鄰接矩陣 中 元素位置 有關(guān) , 沒有其它意義 ;
- 在下面的 鄰接矩陣 中 , 查找 A 的第一個 鄰接結(jié)點 , 從 A 的那一排 第 0 排開始查找 , 第一個為 1 的元素就是 對應(yīng) 第一個 鄰接結(jié)點 )
查詢鄰接節(jié)點 B 是否存在 ; 鄰接節(jié)點 B 結(jié)點存在 ;
查詢鄰接節(jié)點 B 是否被訪問 ; 鄰接節(jié)點 B 結(jié)點存在 并且 沒有被訪問 , 那么 對 鄰接節(jié)點 B 結(jié)點 進(jìn)行 深度優(yōu)先遍歷 , 將 鄰接節(jié)點 B 結(jié)點 作為 新的 初始結(jié)點 , 從 ① 步驟開始執(zhí)行 ;
2、第二輪遞歸
訪問 初始結(jié)點 B , 并將該 初始結(jié)點 B 標(biāo)記為 " 已訪問 " ;
查找 初始結(jié)點 B 的 第一個 鄰接節(jié)點 A ;
- 鄰接結(jié)點選擇 : 這里的 第一個鄰接節(jié)點 選擇 , 是在內(nèi)存數(shù)據(jù) 鄰接表 中排列在首位 0 索引的節(jié)點 , 或者 與 鄰接矩陣 中 元素位置 有關(guān) , 沒有其它意義 ;
- 在下面的 鄰接矩陣 中 , 查找 B 的第一個 鄰接結(jié)點 , 從 B 的那一排 第 1 排開始查找 , 第一個為 1 的元素 對應(yīng)的 是 A 節(jié)點 ;
查詢鄰接節(jié)點 A 是否存在 ; 鄰接節(jié)點 A 結(jié)點存在 ;
查詢鄰接節(jié)點 A 是否被訪問 ; 鄰接節(jié)點 A 結(jié)點 存在 但是 被訪問了 , 那么 查找 B 結(jié)點的 下一個 鄰接節(jié)點 , 轉(zhuǎn)到步驟 ③ 執(zhí)行 ;
查找 結(jié)點 B 的 第二個 鄰接節(jié)點 C ;
- 鄰接結(jié)點選擇 : 這里的 第一個鄰接節(jié)點 選擇 , 是在內(nèi)存數(shù)據(jù) 鄰接表 中排列在首位 0 索引的節(jié)點 , 或者 與 鄰接矩陣 中 元素位置 有關(guān) , 沒有其它意義 ;
- 在下面的 鄰接矩陣 中 , 查找 B 的第二個 鄰接結(jié)點 , 從 B 的那一排 第 1 排開始查找 , 第二個為 1 的元素 對應(yīng)的 是 C 節(jié)點 ;
查詢鄰接節(jié)點 C 是否存在 ; 鄰接節(jié)點 C 結(jié)點存在 ;
查詢鄰接節(jié)點 C 是否被訪問 ; 鄰接節(jié)點 C 結(jié)點存在 并且 沒有被訪問 , 那么 對 鄰接節(jié)點 C 結(jié)點 進(jìn)行 深度優(yōu)先遍歷 , 將 鄰接節(jié)點 C 結(jié)點 作為 新的 初始結(jié)點 , 從 ① 步驟開始執(zhí)行 ;
3、第三輪遞歸
訪問 初始結(jié)點 C , 并將該 初始結(jié)點 C 標(biāo)記為 " 已訪問 " ;
查找 初始結(jié)點 C 的 第一個 鄰接節(jié)點 A ;
- 鄰接結(jié)點選擇 : 這里的 第一個鄰接節(jié)點 選擇 , 是在內(nèi)存數(shù)據(jù) 鄰接表 中排列在首位 0 索引的節(jié)點 , 或者 與 鄰接矩陣 中 元素位置 有關(guān) , 沒有其它意義 ;
- 在下面的 鄰接矩陣 中 , 查找 C 的第一個 鄰接結(jié)點 , 從 C 的那一排 第 2 排開始查找 , 第一個為 1 的元素就是 對應(yīng) 第一個 鄰接結(jié)點 ;
查詢鄰接節(jié)點 A 是否存在 ; 鄰接節(jié)點 A 結(jié)點存在 ;
查詢鄰接節(jié)點 A 是否被訪問 ; 鄰接節(jié)點 A 結(jié)點 存在 但是 被訪問了 , 那么 查找 C 結(jié)點的 下一個 鄰接節(jié)點 , 轉(zhuǎn)到步驟 ③ 執(zhí)行 ;
查找 結(jié)點 C 的 第二個 鄰接節(jié)點 B ;
- 鄰接結(jié)點選擇 : 這里的 第一個鄰接節(jié)點 選擇 , 是在內(nèi)存數(shù)據(jù) 鄰接表 中排列在首位 0 索引的節(jié)點 , 或者 與 鄰接矩陣 中 元素位置 有關(guān) , 沒有其它意義 ;
- 在下面的 鄰接矩陣 中 , 查找 C 的第二個 鄰接結(jié)點 , 從 C 的那一排 第 2 排開始查找 , 第二個為 1 的元素就是 對應(yīng) 第二個 鄰接結(jié)點 ;
查詢鄰接節(jié)點 B 是否存在 ; 鄰接節(jié)點 B 結(jié)點存在 ;
查詢鄰接節(jié)點 B 是否被訪問 ; 鄰接節(jié)點 B 結(jié)點 存在 但是 被訪問了 , 那么 查找 C 結(jié)點的 下一個 鄰接節(jié)點 , 轉(zhuǎn)到步驟 ③ 執(zhí)行 ;
查找 結(jié)點 C 的 第三個 鄰接節(jié)點 ;
- 鄰接結(jié)點選擇 : 這里的 第一個鄰接節(jié)點 選擇 , 是在內(nèi)存數(shù)據(jù) 鄰接表 中排列在首位 0 索引的節(jié)點 , 或者 與 鄰接矩陣 中 元素位置 有關(guān) , 沒有其它意義 ;
- 在下面的 鄰接矩陣 中 , 查找 C 的第三個 鄰接結(jié)點 , 從 C 的那一排 第 2 排開始查找 , 第三個為 1 的元素就是 對應(yīng) 第三個 鄰接結(jié)點 ;
C 的第三個 鄰接結(jié)點 不存在 , 回到 ① 查找 初始結(jié)點 B 的下一個 鄰接節(jié)點 ;
4、第四輪遞歸
在 第二輪遞歸 中 , 已經(jīng)查找了 B 的 2 個鄰接結(jié)點了 , 開始查找 B 的 第 3 個鄰接結(jié)點 ;
查找 結(jié)點 B 的 第三個 鄰接節(jié)點 D ;
- 鄰接結(jié)點選擇 : 這里的 第一個鄰接節(jié)點 選擇 , 是在內(nèi)存數(shù)據(jù) 鄰接表 中排列在首位 0 索引的節(jié)點 , 或者 與 鄰接矩陣 中 元素位置 有關(guān) , 沒有其它意義 ;
- 在下面的 鄰接矩陣 中 , 查找 B 的第三個 鄰接結(jié)點 , 從 B 的那一排 第 1 排開始查找 , 第三個為 1 的元素 對應(yīng)的 是 D 節(jié)點 ;
查詢鄰接節(jié)點 D 是否存在 ; 鄰接節(jié)點 D 結(jié)點存在 ;
查詢鄰接節(jié)點 D 是否被訪問 ; 鄰接節(jié)點 D 結(jié)點存在 并且 沒有被訪問 , 那么 對 鄰接節(jié)點 D 結(jié)點 進(jìn)行 深度優(yōu)先遍歷 , 將 鄰接節(jié)點 D 結(jié)點 作為 新的 初始結(jié)點 , 從 ① 步驟開始執(zhí)行 ;
5、第五輪遞歸
訪問 初始結(jié)點 D , 并將該 初始結(jié)點 D 標(biāo)記為 " 已訪問 " ;
查找 初始結(jié)點 D 的 第一個 鄰接節(jié)點 B ;
- 鄰接結(jié)點選擇 : 這里的 第一個鄰接節(jié)點 選擇 , 是在內(nèi)存數(shù)據(jù) 鄰接表 中排列在首位 0 索引的節(jié)點 , 或者 與 鄰接矩陣 中 元素位置 有關(guān) , 沒有其它意義 ;
- 在下面的 鄰接矩陣 中 , 查找 D 的第一個 鄰接結(jié)點 , 從 D 的那一排 第 3 排開始查找 , 第一個為 1 的元素就是 對應(yīng) 第一個 鄰接結(jié)點 B ;
查詢鄰接節(jié)點 B 是否存在 ; 鄰接節(jié)點 B 結(jié)點存在 ;
查詢鄰接節(jié)點 B 是否被訪問 ; 鄰接節(jié)點 B 結(jié)點 存在 但是 被訪問了 , 那么 查找 D 結(jié)點的 下一個 鄰接節(jié)點 , 轉(zhuǎn)到步驟 ③ 執(zhí)行 ;
查找 結(jié)點 D 的 第二個 鄰接節(jié)點 ;
- 鄰接結(jié)點選擇 : 這里的 第一個鄰接節(jié)點 選擇 , 是在內(nèi)存數(shù)據(jù) 鄰接表 中排列在首位 0 索引的節(jié)點 , 或者 與 鄰接矩陣 中 元素位置 有關(guān) , 沒有其它意義 ;
- 在下面的 鄰接矩陣 中 , 查找 D 的第二個 鄰接結(jié)點 , 從 D 的那一排 第 3 排開始查找 , 第二個為 1 的元素就是 對應(yīng) 第二個 鄰接結(jié)點 ;
D 的第三個 鄰接結(jié)點 不存在 , 回到 ① 查找 初始結(jié)點 B 的下一個 鄰接節(jié)點 ; 
6、第六輪遞歸
在 第四輪遞歸 中 , 已經(jīng)查找了 B 的 3 個鄰接結(jié)點了 , 開始查找 B 的 第 4 個鄰接結(jié)點 ;
查找 結(jié)點 B 的 第四個 鄰接節(jié)點 E ;
- 鄰接結(jié)點選擇 : 這里的 第一個鄰接節(jié)點 選擇 , 是在內(nèi)存數(shù)據(jù) 鄰接表 中排列在首位 0 索引的節(jié)點 , 或者 與 鄰接矩陣 中 元素位置 有關(guān) , 沒有其它意義 ;
- 在下面的 鄰接矩陣 中 , 查找 B 的第四個 鄰接結(jié)點 , 從 B 的那一排 第 1 排開始查找 , 第四個為 1 的元素 對應(yīng)的 是 E 節(jié)點 ;
查詢鄰接節(jié)點 E 是否存在 ; 鄰接節(jié)點 E 結(jié)點存在 ;
查詢鄰接節(jié)點 E 是否被訪問 ; 鄰接節(jié)點 E 結(jié)點存在 并且 沒有被訪問 , 那么 對 鄰接節(jié)點 E 結(jié)點 進(jìn)行 深度優(yōu)先遍歷 , 將 鄰接節(jié)點 E 結(jié)點 作為 新的 初始結(jié)點 , 從 ① 步驟開始執(zhí)行 ;
7、第七輪遞歸
訪問 初始結(jié)點 E , 并將該 初始結(jié)點 E 標(biāo)記為 " 已訪問 " ;
查找 初始結(jié)點 E 的 第一個 鄰接節(jié)點 B ;
- 鄰接結(jié)點選擇 : 這里的 第一個鄰接節(jié)點 選擇 , 是在內(nèi)存數(shù)據(jù) 鄰接表 中排列在首位 0 索引的節(jié)點 , 或者 與 鄰接矩陣 中 元素位置 有關(guān) , 沒有其它意義 ;
- 在下面的 鄰接矩陣 中 , 查找 E 的第一個 鄰接結(jié)點 , 從 E 的那一排 第 4 排開始查找 , 第一個為 1 的元素就是 對應(yīng) 第一個 鄰接結(jié)點 B ;
查詢鄰接節(jié)點 B 是否存在 ; 鄰接節(jié)點 B 結(jié)點存在 ;
查詢鄰接節(jié)點 B 是否被訪問 ; 鄰接節(jié)點 B 結(jié)點 存在 但是 被訪問了 , 那么 查找 D 結(jié)點的 下一個 鄰接節(jié)點 , 轉(zhuǎn)到步驟 ③ 執(zhí)行 ;
查找 結(jié)點 B 的 第五個 鄰接節(jié)點 ;
- 鄰接結(jié)點選擇 : 這里的 第一個鄰接節(jié)點 選擇 , 是在內(nèi)存數(shù)據(jù) 鄰接表 中排列在首位 0 索引的節(jié)點 , 或者 與 鄰接矩陣 中 元素位置 有關(guān) , 沒有其它意義 ;
- 在下面的 鄰接矩陣 中 , 查找 B 的第五個 鄰接結(jié)點 , 從 B 的那一排 第 3 排開始查找 , 第五個為 1 的元素就是 對應(yīng) 第二個 鄰接結(jié)點 ;
B 的第五個 鄰接結(jié)點 不存在 , 回到 ① 查找 初始結(jié)點 A 的下一個 鄰接節(jié)點 ;
文章來源：http://www.zghlxwxcb.cn/news/detail-781988.html
繼續(xù)回溯到 A 結(jié)點 , 查找 A 結(jié)點的 第二個 鄰接結(jié)點 C , 然后 以 C 為初始結(jié)點繼續(xù)進(jìn)行遍歷 , 進(jìn)行回溯 , 所有的結(jié)點都已經(jīng)遍歷 , 遞歸結(jié)束 ;文章來源地址http://www.zghlxwxcb.cn/news/detail-781988.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】圖遍歷算法 ( 深度優(yōu)先搜索 DFS | 深度優(yōu)先搜索和廣度優(yōu)先搜索 | 深度優(yōu)先搜索基本思想 | 深度優(yōu)先搜索算法步驟 | 深度優(yōu)先搜索理論示例 )的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
