BFS/DFS final path 求解答

depth-first search(dfs，深度優先搜尋)

lty92124 2019-08-02 11:57:13 ‧ 2412 瀏覽

Use proper data structure to show the BFS/DFS final path of the following graph (see Figure 3) starts from node ‘u’.
https://drive.google.com/file/d/1aEYEhb_19cT1z4joXQEV_tP4CZyfEQJF/view?usp=sharing

直播研討會

{{ item.channelVendor }} {{ item.webinarstarted }} |

直播中

丹尼爾胡

iT邦新手 4 級 ‧ 2019-09-04 06:58:36

這個問題看起來有點像學校作業（如果不是的話抱歉，請糾正我XD），所以我不會直接寫出答案。

Breadth-first Search(BFS)和Depth-first Search(DFS)的演算法長得非常相似，幾乎可以用同一個function去解。
兩者的差別在於資料結構的儲存方式：

BFS：隊Queue，FIFO (First-in-First-out)
DFS：棧Stack，LIFO (Last-in-First-Out)
也因為兩者資料暫存方式的不同，使得他們有不一樣的搜尋方式：
BFS會把所在位置上的所有可能的下一步(possible successor)都找出來，接著把這個位置從Queue中推出去，再照著寫入順序找下一個，並做同一件事，直到找到目標(Goal State)，或是拓展完整個Graph。
DFS則會在找到第一個下一步(successor)之後，從那個successor的位置上再找下一個successor，一路找下去，若是這條路走到最後沒有走到目標，則回到最後一個點的上一個點，看看它還有沒有其他successor，一路走回到起始點(Initial State)。

說再多其實都不比看一段影片來的有印象：
DFS