作者BNMAA (o,o,o)
看板Army-Sir
標題[問題] 99計概第34題
時間Thu Feb 4 13:40:05 2010
按照題目所給的graph
A
/ \
B C
/ \ \
D-E----F
既沒指定DFS的起點
也沒說明訪問鄰居的順序
好吧 四個選項都是A開頭 算它有指定起點為A好了
那 (B)ABDEFC 跟 (C)ACFEDB 都是合法的DFS走訪順序
對於tree來講 DFS就是preorder traversal
但這題的graph並不是tree阿阿阿~~
只因為它畫起來長得跟tree有點像 就要先走左邊嗎？
本科系的寫到這題應該都會眉頭一皺吧...?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.240.242.207
1F：→ DragonDeath:這題完全不懂啊 02/04 13:42
2F：推 topractise:之前修資結的印象 都從左邊先走...一次走到底 02/04 13:42
3F：→ Liroy:洪兔沒教你說字母前面的先走起嗎XD 02/04 13:43
4F：推 b90738:沒說是中序？後序？前序？ 所以我把它當中序＝＝！ 02/04 13:46
5F：→ BNMAA:2F: 樹習慣是這樣 但這題不是樹 02/04 13:47
6F：→ BNMAA:3F: DFS沒有這種規定 端看鄰居的list怎麼maintain 02/04 13:48
7F：推 RoyalWalker:這題是真的不會，算此次的難題之一吧 02/04 14:06
8F：推 cjcat2266:這題我就BC二猜一，然後猜錯了 = = 02/04 14:15
9F：→ cjcat2266:我還是覺得兩種都是合法的DFS啊 02/04 14:16
10F：推 lcd0507:這有兩個答案吧 02/04 14:18
11F：推 RoyalWalker:跟樹無關喔，這不是樹的走訪，有篇文我看了就覺得沒錯 02/04 14:32
13F：→ RoyalWalker:雖然也寫錯了，當作學到一件事好了... 02/04 14:34
14F：→ RoyalWalker:6F_BNMAA:文中說「DFS通常也會有著循序、漸增的特質」 02/04 14:36
15F：推 topractise:(原來我是賽對的) 02/04 14:38
16F：推 tulian:賽對+1 02/04 14:42
17F：推 tcf:就理論上來說DFS是不會唯一,但是這是考試不得已還是選B好 02/04 14:43
18F：推 lcd0507:如果用陣列來實作或許會符合循序漸增 02/04 15:50
19F：→ lcd0507:用adjacent list 就要看node擺的位置不一定按照順序吧?? 02/04 15:51
20F：→ lcd0507:如果照書上演算法寫的定義應該bc都對吧 02/04 15:52
21F：推 jeff30133:就把英文字母當做優先順序 不然ㄧ開始從A幹嘛 02/04 16:04
22F：→ BNMAA:to R:那是nonsense 我迴圈也可以從後面跑回來 02/04 16:14
23F：推 chieher:j大胡扯 = = A是因為他是root 02/04 16:14
24F：→ BNMAA:for (i = |N(v)| - 1; i >= 0; i--) dfs_visit(N(v)[i]); 02/04 16:15
25F：→ BNMAA:這題根本就沒人規定提取鄰居的priority如何決定 02/04 16:15
26F：→ BNMAA:怎麼能說DFS出來的序列是唯一？ 02/04 16:15
27F：→ BNMAA:我的看法同lcd0507 02/04 16:18
※ 編輯: BNMAA 來自: 123.240.242.207 (02/04 16:18)
28F：推 bnsblue:graph沒有root.tree才有 從A來是因為他四個選項都是A先= = 02/04 16:29
29F：推 frouscy:純推香蕉 真的是眉頭一皺 XD 02/04 17:31
30F：推 chevalierxd:我猜B耶~~這題有問題啦(敲碗) 02/04 22:15
31F：推 tchuangtom:這題B或C都可給對,但不該送分,因題目沒有問題 02/05 00:44
32F：推 Leeng:BC都可以吧 02/05 00:55