作者turnoff11 (好想打排球)
看板CSSE
标题Re: [问题] 资料结构中的DFS（Depth first searchꄠ…
时间Wed Sep 23 11:56:47 2009
※ 引述《MuadDib (Muaddib)》之铭言：
: 你在考虑graph的时候不能以tree的角度去看
: graph是没有深度的
: 而graph和tree最大的不同就是graph有cycle/loop而tree没有
: 所以你实作的时候需要mark的机制来避免重复搜寻的无限回圈
: 所以DFS简单来说 就是选一个点当root
: 然後搜寻他其中一个neighbor 再从neighbor里面搜寻未被marked/visited的neighbor
: 不断循环 直到目前的node已经没有未被marked/visited的neighbor
: 就做backtrack (回到前一个node) 然後继续找neighbor
: backtrack有很多种做法 像是stack, recursive function(太深可能会记忆体不足),
: right-threaded binary tree(引线二元树) 等等
: 以你的例子来说 1是root 也就是起点
: 先visit root 然後找neighbor 有2, 3, 5
: 通常这种图都是照数字大小顺序来visit
: 所以选择visit 2
: 之後找2的neighbor 就是4
: 再找4的neighbor 就是8 (这边我看好久才发现他那条线其实是连到8而不是4 画的并不好)
: 再找8的neighbor 有5, 6, 7
: 先visit 5 之後发现5没有未visited neighbor 所以又backtrack至8
: 再找8的neighbor 剩下6, 7 以此类推...
这样子看起来
似乎跟所谓的深度没有太大的关系
都只是在找寻所谓的neighbor
而且都是从数字小到大在搜寻
这样子如果同样的例子换成是bfs来算
是不是也是一样的答案呢？
麻烦大大帮我解释一下罗
感恩
--
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 163.30.170.179
1F：→ dendrobium:BFS => 1 2 3 5 4 6 8 7 差很多 09/23 13:55
2F：推 MuadDib:BFS是neighbor先全部找完才开始找neighbor's neighbor 09/23 20:12
3F：→ MuadDib:DFS是root->neighbor->neighbor's neighbor 一直线找下去 09/23 20:13
4F：→ turnoff11:谢谢大大，我终於明白了~感恩，你们都是大好人 09/24 10:42
5F：→ turnoff11:另外推一个网址，里面可以使用自己的图来做BFS和DFS 09/24 10:43