1，BFS

可以求解最短路徑等?最優(yōu)解?問題

BFS? 先進(jìn)先出

在程序?qū)崿F(xiàn) BFS 時(shí)需要考慮以下問題：

隊(duì)列：用來存儲(chǔ)每一輪遍歷得到的節(jié)點(diǎn)；

標(biāo)記：對(duì)于遍歷過的節(jié)點(diǎn)，應(yīng)該將它標(biāo)記，防止重復(fù)遍歷

?path?=?[[0,0]]? ? ##頭結(jié)點(diǎn)放入

????????while?path:

????????????for?_?in?range(len(path)):? ?遍歷每一層節(jié)點(diǎn)

????????????????for?new_x,?new_y?in?[[x?-?1,?y?-?1],?[x?-?1,?y],?[x?-?1,?y?+?1],?[x,?y?-?1],

?????????????????????????????????????[x,?y?+?1],?[x?+?1,?y?-?1],?[x?+?1,?y],?[x?+?1,?y?+?1]]:? #幾個(gè)方向的遍歷

? ? ? ? ? ? ? ? ? ? ? ? ? ? 各種邊界條件的判斷

? ? ? ? ? ? ? ? ? ? ? ? ? ? 將新的節(jié)點(diǎn)加path

2,DFS

在程序?qū)崿F(xiàn) DFS 時(shí)需要考慮以下問題：

棧：用棧來保存當(dāng)前節(jié)點(diǎn)信息，當(dāng)遍歷新節(jié)點(diǎn)返回時(shí)能夠繼續(xù)遍歷當(dāng)前節(jié)點(diǎn)?？梢允褂眠f歸棧。

標(biāo)記：和 BFS 一樣同樣需要對(duì)已經(jīng)遍歷過的節(jié)點(diǎn)進(jìn)行標(biāo)記。

先進(jìn)后出

帶數(shù)組的版本

不帶數(shù)組，用遞歸代替