Re: [演算] 深度優先搜尋

看板CSSE (電腦科學及軟體工程)作者micklin (mick)時間10月前 (2023/06/15 00:28)推噓3(3推 0噓 10→)

留言13則, 2人參與討論串2/2 (看更多)

※ 引述《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://www.ptt.cc/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://www.ptt.cc/bbs/CSSE/M.1686760080.A.4D5.html

推

LPH66

06/15 07:13, 10月前 , 1^F

06/15 07:13, 1^F

→

LPH66

06/15 07:13, 10月前 , 2^F

06/15 07:13, 2^F

→

LPH66

06/15 07:13, 10月前 , 3^F

06/15 07:13, 3^F