圖的兩種遍歷方式：

1. 深度優(yōu)先遍歷（DFS——Depth First Search）
2. 廣度優(yōu)先遍歷（BFS——Breath First Search）

圖的遍歷算法里，處理臨時(shí)數(shù)據(jù)，依賴兩個(gè)抽象數(shù)據(jù)結(jié)構(gòu)：

• 棧
• 隊(duì)列

廣度優(yōu)先的動(dòng)態(tài)圖

廣度優(yōu)先遍歷也叫層序遍歷，先遍歷第一層(節(jié)點(diǎn) 1)，再遍歷第二層(節(jié)點(diǎn) 2，3，4)，第三層(5，6，7，8)，第四層(9，10)。

深度優(yōu)先的動(dòng)態(tài)圖

從根結(jié)點(diǎn)出發(fā)，一直向左子節(jié)點(diǎn)走，直到左子節(jié)點(diǎn)不存在然后返回到上一個(gè)節(jié)點(diǎn)走這個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)，然后一直往右子節(jié)點(diǎn)走，同樣的也是走不通為止就返回。很顯然這種一路走到黑，黑了就回頭的方式，就是深度優(yōu)先遍歷的過程。

廣度和深度的具體步驟

廣度搜索中，存儲(chǔ)下層的數(shù)據(jù)需要用到隊(duì)列，
深度搜索中，存儲(chǔ)一整條路徑的數(shù)據(jù)，需要用到棧 ，用棧去回溯到最開始的頂點(diǎn)，
具體步驟去看《秒懂算法：用常識(shí)解讀數(shù)據(jù)結(jié)構(gòu)》，我覺得書分解得很詳細(xì)了，不需要在搬一次了。

深度和廣度的應(yīng)用場景

我面試過挺多次的，很多面試問題都慢慢淡忘了，但是有一個(gè)問題一直記得：
他問，你平時(shí)在做爬蟲的時(shí)候，用深度還是廣度？

現(xiàn)在回想起來，覺得他問得真扯淡。

為什么？

選擇深度或廣度所對(duì)應(yīng)的是不同場景，理論上來說，所有問題，都可以用list解決，但是為什么還要分化出那么多的數(shù)據(jù)結(jié)構(gòu)？

還不是因?yàn)椤?strong>不同的問題，采用不同的數(shù)據(jù)結(jié)構(gòu)，這樣解決效率才高，資源才省。

比如看這個(gè)下面這個(gè)家族結(jié)構(gòu)圖：

如果想要找到曾祖母Ruby的所有兒女，那么用深度還是廣度？

• 肯定是廣度最合適。
  使用廣度優(yōu)先搜索，那么立刻就能找到她所有直接女兒(Andrea、Xander、CoCo和Maya)，不用搜索和她相隔一代的親人。

如果想要找到Ruby的一個(gè)叫Ruth的后代，用深度還是廣度？

• 顯然是深度合適。
  用深度優(yōu)先搜索，則可以馬上移動(dòng)到圖的底部，在幾步之內(nèi)就能找到曾孫一輩。
  雖然還是需要遍歷整幅圖才能找到Ruth，但至少快速找到她是有可能的。而用廣度優(yōu)先搜索則別無選擇，必須遍歷前兩輩的所有人，才能開始搜索曾孫這一輩。

在思考用深度還是廣度時(shí)？應(yīng)該是先思考究竟是想先盡可能在初始頂點(diǎn)附近搜索，還是想先盡可能遠(yuǎn)離它？

• 前者適合用廣度優(yōu)先搜索
• 后者適合用深度優(yōu)先搜索。

所以，為什么我覺得那個(gè)問得很扯淡，就類似：“郭純，你喜歡用list還是Map呀？”

“- -。”