作者future1234 (Low)
看板TransCSI
标题Re: [心得] 政大资科97年计概解答(第肆题)
时间Wed Jul 1 23:52:21 2009
(庚) m b g d u p s x
(辛) b d g m p s u x
(壬) d g b s p x u m
(癸) 0
(子) 没有答案
1F:→ zptdaniel:癸的话 pre、in、post 不都是走DFS吗?都会一直往左下走 07/01 22:10
2F:→ zptdaniel:然後再慢慢往上? 07/01 22:11
癸 这题我的想法是
m
/ \
b u
\ / \
g p x
/ \
d s
走 pre , 依照DFS的定义一定可行
走 in- , 以b为起点 , b 到 d 就error了 (b还能走 m 跟 g) , 不符合DFS走法
走 post, 以d为起点 , d->g->b , 到b之前 ok , b还可以走 m , 却跳到 s , 不符合DFS走法
我找一段网路上对於DFS的定义
depth-first search 是以某一节点为出发点,不断地前进拜访未曾被拜访过的节点,直到无路可走或是所有相邻的节点都已经拜访过为止
,然後再退回前一个节点,寻找没有拜访过的节点,直到所有相邻的节点都已被拜访过。
另参考例子:
http://nthucad.cs.nthu.edu.tw/~yyliu/personal/nou/04ds/dfs.html
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.119.162.51
※ 编辑: future1234 来自: 140.119.162.51 (07/01 23:53)