寬度優(yōu)先
寬度優(yōu)先搜索算法(又稱廣度優(yōu)先搜索)是最簡便的圖的搜索算法之一,這一算法也是很多重要的圖的算法的原型。其別名又叫BFS,屬于一種盲目搜尋法,目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點(diǎn),以找尋結(jié)果。
換句話說,它并不考慮結(jié)果的可能位置,徹底地搜索整張圖,直到找到結(jié)果為止。簡單來說,bfs好像是一個(gè)耳聽六路眼觀八方的人,搜索時(shí)是一層一層的搜索的。BFS利用的數(shù)據(jù)結(jié)構(gòu)是queue,空間復(fù)雜度為o(2^n),另外BFS可以用來解決最短路問題。BFS是一個(gè)從近到遠(yuǎn)的擴(kuò)散過程。