Re: [心得] 政大資科97年計概解答(第肆題)

[future1234 (Low)]

(庚) 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
(子) 沒有答案


→ zptdaniel:癸的話 pre、in、post 不都是走DFS嗎?都會一直往左下走
→ zptdaniel:然後再慢慢往上?
癸 這題我的想法是

       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)