廣度優(yōu)先搜索(BFS)

廣度優(yōu)先搜索一層一層地進(jìn)行遍歷，每層遍歷都以上一層遍歷的結(jié)果作為起點(diǎn)，遍歷一個距離能訪問到的所有節(jié)點(diǎn)。需要注意的是，遍歷過的節(jié)點(diǎn)不能再次被遍歷。

第一層：
0 -> {6,2,1,5}

第二層：
6 -> {4}
2 -> {}
1 -> {}
5 -> {3}

第三層：
4 -> {}
3 -> {}

每一層遍歷的節(jié)點(diǎn)都與根節(jié)點(diǎn)距離相同。設(shè) di 表示第 i 個節(jié)點(diǎn)與根節(jié)點(diǎn)的距離，推導(dǎo)出一個結(jié)論：對于先遍歷的節(jié)點(diǎn) i 與后遍歷的節(jié)點(diǎn) j，有 di <= dj。利用這個結(jié)論，可以求解最短路徑等 最優(yōu)解 問題：第一次遍歷到目的節(jié)點(diǎn)，其所經(jīng)過的路徑為最短路徑。應(yīng)該注意的是，使用 BFS 只能求解無權(quán)圖的最短路徑，無權(quán)圖是指從一個節(jié)點(diǎn)到另一個節(jié)點(diǎn)的代價都記為 1。

在程序?qū)崿F(xiàn) BFS 時需要考慮以下問題：
隊(duì)列：用來存儲每一輪遍歷得到的節(jié)點(diǎn)；
標(biāo)記：對于遍歷過的節(jié)點(diǎn)，應(yīng)該將它標(biāo)記，防止重復(fù)遍歷。

深度優(yōu)先搜索(DFS)

廣度優(yōu)先搜索一層一層遍歷，每一層得到的所有新節(jié)點(diǎn)，要用隊(duì)列存儲起來以備下一層遍歷的時候再遍歷。

而深度優(yōu)先搜索在得到一個新節(jié)點(diǎn)時立即對新節(jié)點(diǎn)進(jìn)行遍歷：從節(jié)點(diǎn) 0 出發(fā)開始遍歷，得到到新節(jié)點(diǎn) 6 時，立馬對新節(jié)點(diǎn) 6 進(jìn)行遍歷，得到新節(jié)點(diǎn) 4；如此反復(fù)以這種方式遍歷新節(jié)點(diǎn)，直到?jīng)]有新節(jié)點(diǎn)了，此時返回。返回到根節(jié)點(diǎn) 0 的情況是，繼續(xù)對根節(jié)點(diǎn) 0 進(jìn)行遍歷，得到新節(jié)點(diǎn) 2，然后繼續(xù)以上步驟。

從一個節(jié)點(diǎn)出發(fā)，使用 DFS 對一個圖進(jìn)行遍歷時，能夠遍歷到的節(jié)點(diǎn)都是從初始節(jié)點(diǎn)可達(dá)的，DFS 常用來求解這種 可達(dá)性 問題。

在程序?qū)崿F(xiàn) DFS 時需要考慮以下問題：
棧：用棧來保存當(dāng)前節(jié)點(diǎn)信息，當(dāng)遍歷新節(jié)點(diǎn)返回時能夠繼續(xù)遍歷當(dāng)前節(jié)點(diǎn)?？梢允褂眠f歸棧。
標(biāo)記：和 BFS 一樣同樣需要對已經(jīng)遍歷過的節(jié)點(diǎn)進(jìn)行標(biāo)記。

回溯(BackTracking)

回溯屬于DFS
· 普通DFS主要用在可達(dá)性問題，這種問題只需要執(zhí)行到特點(diǎn)的位置然后返回即可；
· 而Backtracking主要用于求解排列組合問題，例如有{'a', 'b', 'c'}三個字符，求解所有由這三個字符排列得到的字符串，這種問題在執(zhí)行到特定的位置返回之后還會繼續(xù)執(zhí)行求解過程。

因?yàn)锽acktracking不是立即返回，而要繼續(xù)求解，因此在程序?qū)崿F(xiàn)時，需要注意對元素的標(biāo)記問題：
· 在訪問一個新元素進(jìn)入新的遞歸調(diào)用時，需要將新元素標(biāo)記為已經(jīng)訪問，這樣才能在繼續(xù)遞歸調(diào)用時不用重復(fù)訪問該元素；
· 但是在遞歸返回時，需要將元素標(biāo)記為未訪問，因?yàn)橹恍枰ＷC在一個遞歸鏈中不同時訪問一個元素，但可以訪問已經(jīng)訪問過的但不在當(dāng)前遞歸鏈中的元素。