※ 引述《s7917313 (欸你過來一夏)》之銘言:
: 標題: [演算] 深度優先搜尋
: 時間: Fri May 12 02:54:41 2023
:
: 各位大大好 小弟最近在複習深度優先搜尋(DFS)時發現了個問題
:
: 一直以來我對DFS的理解是只要該點還能走向下一個節點就繼續走 若無路可走或是下個節
: 點都走過了就回到上一個節點
:
: 直到我看了這篇文章
: https://ithelp.ithome.com.tw/m/articles/10281404?sc=iThelpR
:
: 以此圖為例
: https://i.imgur.com/sKefHNC.jpg
: 假設我已經走訪了AEC三個點(以A為起點)照我的想法應該先把B走訪完再回到E點往下走
用stack是為了把"等一下要檢查的點"都存起來等一下要用。
stack: A
動作 pop A
stack E
D
B
動作 pop E , 從圖來看E可以連到ACDF, 但明顯的A不用放進去再檢查, D也早在stack裡
stack F
C
D
B
動作 pop F, F跟E有連, 但不會把E再放一次
動作 pop C, 有連的是BE, B在stack, E有走過
動作 pop D, 有連的是AE, 都走過了
動作 pop B, 有連的是AC, 都走過了
所以順序是 AEFCDB
:
: 也就是AECB 應該沒有別的選擇才對
因為你用眼睛在走,就沒有stack "等一下再看"的概念
:
: 可是若用文章作者stack的方式去實作
: B卻是最後才走訪
: 主要原因在於走訪A的時候 B就被放在stack最底下 導致了B一定是最後走訪嗎?
:
: 這問題讓我好疑惑
: 小的初學 若有觀念錯誤的地方再麻煩指教
:
: