[其他] 深度優先搜尋 (堆疊方式)

看板Math作者 (選ばれし子どもたち)時間4年前 (2021/05/29 19:18), 4年前編輯推噓3(3推 0噓 7→)
留言10則, 1人參與, 4年前最新討論串1/1
https://imgur.com/a/3j1Gism 不好意思請教神人大大 第二小題，右邊參考解答中 為何需要把趙六放入推疊三次? 還是解答有誤? 願奉上P幣100P -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.166.103.246 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1622287135.A.E43.html
推
05/29 19:50, 4年前 , 1F
我們只在走到節點時紀錄走過, 而不是在推進堆疊時
05/29 19:50, 1F
→
05/29 19:53, 4年前 , 2F
另外, 這三個堆疊紀錄代表不同來源, 而 DFS 要的
05/29 19:53, 2F
→
05/29 19:54, 4年前 , 3F
是從最深點的分支先走, 因此 (5) 的趙六來自 (4)
05/29 19:54, 3F
→
05/29 19:55, 4年前 , 4F
先進行, 而 (6) 來自 (3), (7) 來自 (2) 則當作重覆
05/29 19:55, 4F
請問這題的答案是唯一嗎? 感謝您，已匯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
推
05/29 20:55, 4年前 , 5F
你在尋訪張三時就要把它的所有連線推進堆疊了
05/29 20:55, 5F
→
05/29 20:55, 4年前 , 6F
所以不能只在那裡推趙六, 連李四也要推進去
05/29 20:55, 6F
→
05/29 20:55, 4年前 , 7F
而推的順序即是題目要求的順序
05/29 20:55, 7F
→
05/29 20:56, 4年前 , 8F
因此先推趙六再推李四
05/29 20:56, 8F
推
05/29 20:57, 4年前 , 9F
同理, 尋訪李四時要把它的所有連線推進去
05/29 20:57, 9F
→
05/29 20:58, 4年前 , 10F
扣掉張三是走來的方向, 剩下的先推趙六再推王五
05/29 20:58, 10F
‣ 更多 ooww 的文章
文章代碼(AID): #1WiYCVv3 (Math)