作者micklin (mick)
看板CSSE
標題Re: [演算] 深度優先搜尋
時間Thu Jun 15 00:27:56 2023
※ 引述《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一定是最後走訪嗎？
:
: 這問題讓我好疑惑
: 小的初學 若有觀念錯誤的地方再麻煩指教
:
: ----
: Sent from BePTT on my iPhone 8 Plus
:
: --
:
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.9.239.27 (臺灣)
: ※ 文章網址: https://webptt.com/m.aspx?n=bbs/CSSE/M.1683831283.A.293.html
:
: ※ 編輯: s7917313 (101.9.239.27 臺灣), 05/12/2023 02:57:36
:
: ※ 編輯: s7917313 (101.9.239.27 臺灣), 05/12/2023 02:58:35
:
: ※ 編輯: s7917313 (101.9.239.27 臺灣), 05/12/2023 03:01:17
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.85.32 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/CSSE/M.1686760080.A.4D5.html
1F：推 LPH66: 「D也早在stack裡」這句話其實也有一個可能的實作差異 06/15 07:13
2F：→ LPH66: 如果不管有沒有在 stack 裡都推的話順序就又不一樣了 06/15 07:13
3F：→ LPH66: 而之所以會不檢查在不在 stack 裡是因為基本上這會需要 06/15 07:13
4F：→ LPH66: 另外的資料結構來紀錄點是不是已經在 stack 裡 06/15 07:14
5F：→ LPH66: 一般很少會為此再開一個紀錄用結構 (已走過已經需要紀錄了) 06/15 07:14
6F：→ LPH66: 再反過來說, 如果紀錄不是「已走過」而是「已進 stack」 06/15 07:16
7F：→ LPH66: (ie.在推前檢查紀錄) 那才會有「已在 stack 故不推」的邏輯 06/15 07:17
大師好久不見
您是對的，如果Stack很深，不太可能在Stack裡面挖呀挖呀挖就為了看"有沒有在裡面"。
若不做Stack檢查，順序就不大一樣，假設pop過的不會再push，順序會是 AEFDCB
8F：推 s7917313: 所以只是實作上差異,我原本理解的觀念對嗎 或是說我這 06/16 11:37
9F：→ s7917313: 樣的走法有沒有符合DFS 06/16 11:37
10F：推 s7917313: 補充一下我是考國家考試的資料處理的內容 我查詢網路蠻 06/16 11:45
11F：→ s7917313: 多教學都是用眼睛再走 06/16 11:45
12F：→ s7917313: 所以其實這樣是可行的對吧 06/16 11:45
13F：→ s7917313: 就考試來說 06/16 11:45
不太對，DFS也好，BFS也好，不會有走不完的狀況，
您說的"也就是AECB 應該沒有別的選擇才對"，沒走到D就是個怪事。
※ 編輯: micklin (114.32.85.32 臺灣), 06/18/2023 00:07:00
14F：推 caponis: 推！ 01/31 22:33