作者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/cn.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