BFS：廣度優(yōu)先搜索
DFS：深度優(yōu)先搜索
樹的遍歷
BFS：A ? B C D ?E F ?G ?H I
DFS: ?A B ?C E ?F ?D G H ?I
圖的遍歷
從A出發(fā)
BFS：A ?B ?C ?D ?E ?F （其中一種）
DFS：A ?B ?D ?F ?E ?C （其中一種）
數(shù)據(jù)結構
BFS： 隊列（先進先出）
步驟：1睁壁、首先A入隊列汇四，
? ? ? ? ? ? 2幅恋、A出隊列時韭脊，A的鄰接結點B懊缺，C相應進入隊列?
? ? ? ? ? ? 3流部、B出隊列時摹蘑，B的鄰接結點A惊畏，C舀透，D中未進過隊列的D進入隊列
? ? ? ? ? ? 4栓票、C出隊列時，C的鄰接結點A愕够，B走贪，D，E中未進過隊列的E進入隊列
? ? ? ? ? ? 5惑芭、D出隊列時坠狡，D的鄰接結點B，C遂跟，E擦秽，F(xiàn)中未進過隊列的F進入隊列
? ? ? ? ? ? 6、E出隊列漩勤，沒有結點可再進隊列
????????????7感挥、F出隊列
DFS：棧（先進后出）
步驟：1、首先A入棧越败，
? ? ? ? ? ? 2触幼、A出棧時，A的鄰接結點B究飞，C相應入棧? （這里假設C在下置谦，B在上）
? ? ? ? ? ? 3堂鲤、B出棧時，B的鄰接結點A媒峡，C瘟栖，D中未進過棧的D入棧
? ? ? ? ? ? 4、D出棧時谅阿，D的鄰接結點B半哟，C，E签餐，F(xiàn)中未進過棧的E寓涨、F入棧（假設E在下，F(xiàn)在上）
? ? ? ? ? ? 5氯檐、F出棧時戒良，F(xiàn)沒有鄰接結點可入棧
? ? ? ? ? ? 6、E出棧冠摄，E的鄰接結點C糯崎，D已入過棧
????????????7、C出棧
代碼（Python）
1河泳、圖有兩種表示方式拇颅，鄰接矩陣和鄰接表
? ? ? 這里用python字典結構表示:
BFS
DFS
能用棧的地方都能用遞歸
DFS遞歸和非遞歸的結果不同，非遞歸：A C E D F B ? ?遞歸：A B C D E F
此外乔询，深度優(yōu)先搜索和廣度優(yōu)先搜索的結果都不唯一。
參考視頻：https://www.bilibili.com/video/av25763384
