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