※ 引述《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一定是最后走访吗？
:
: 这问题让我好疑惑
: 小的初学 若有观念错误的地方再麻烦指教
:
:

“D也早在stack里”这句话其实也有一个可能的实作差异如果不管有没有在 stack 里都推的话顺序就又不一样了而之所以会不检查在不在 stack 里是因为基本上这会需要另外的资料结构来纪录点是不是已经在 stack 里一般很少会为此再开一个纪录用结构 (已走过已经需要纪录了)再反过来说, 如果纪录不是“已走过”而是“已进 stack”(ie.在推前检查纪录) 那才会有“已在 stack 故不推”的逻辑

所以只是实作上差异,我原本理解的观念对吗 或是说我这样的走法有没有符合DFS补充一下我是考国家考试的资料处理的内容 我查询网络蛮多教学都是用眼睛再走所以其实这样是可行的对吧就考试来说

推！