作者ooww (選ばれし子どもたち)
看板Math
標題[其他] 深度優先搜尋 (堆疊方式)
時間Sat May 29 19:18:53 2021
https://imgur.com/a/3j1Gism
不好意思請教神人大大
第二小題，右邊參考解答中
為何需要把趙六放入推疊三次?
還是解答有誤?
願奉上P幣100P
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.166.103.246 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1622287135.A.E43.html
1F：推 LPH66 : 我們只在走到節點時紀錄走過, 而不是在推進堆疊時 05/29 19:50
2F：→ LPH66 : 另外, 這三個堆疊紀錄代表不同來源, 而 DFS 要的 05/29 19:53
3F：→ LPH66 : 是從最深點的分支先走, 因此 (5) 的趙六來自 (4) 05/29 19:54
4F：→ LPH66 : 先進行, 而 (6) 來自 (3), (7) 來自 (2) 則當作重覆 05/29 19:55
請問這題的答案是唯一嗎?
感謝您，已匯100p
※ 編輯: ooww (218.166.103.246 臺灣), 05/29/2021 20:22:29
請問可否這樣寫?
1. push（張三(CS)）
stack：張三(CS)
2. pop（）→走訪張三(CS)
stack：empty
push（趙六(CL)）
stack：趙六(CL)
3. pop（）→走訪趙六(CL)
stack：empty
push（李四(LS)）
stack：李四(LS)
4. pop→走訪李四(LS)
stack：empty
push（王五(WW)）
stack：王五(WW)
5. pop→走訪王五(WW)
stack：empty
6. 結束
深度優先搜尋的走訪順序：張三→ 趙六→李四→王五
※ 編輯: ooww (218.166.103.246 臺灣), 05/29/2021 20:41:01
5F：推 LPH66 : 你在尋訪張三時就要把它的所有連線推進堆疊了 05/29 20:55
6F：→ LPH66 : 所以不能只在那裡推趙六, 連李四也要推進去 05/29 20:55
7F：→ LPH66 : 而推的順序即是題目要求的順序 05/29 20:55
8F：→ LPH66 : 因此先推趙六再推李四 05/29 20:56
9F：推 LPH66 : 同理, 尋訪李四時要把它的所有連線推進去 05/29 20:57
10F：→ LPH66 : 扣掉張三是走來的方向, 剩下的先推趙六再推王五 05/29 20:58