作者stator (別急著吃棉花糖)
看板EE_DSnP
標題[問題] 請問depth first search的問題
時間Mon Feb 8 16:08:39 2010
因為在研讀的過程中，遇到了一個問題
這是今年彰師大的資管考古題
網址為
http://lib.ncue.edu.tw/exam/98/Tm/im01.pdf
請教各位前輩，在最後一頁最後一題
他要我們畫出spanning tree，深度優先
我所畫的是為
a
/
b c d
/ / \ /
e f g
\ |
h
不知這樣畫是否正確呢?spanning tree的定義是不能有迴路出現
但書上的答案沒有把c-g的那條線畫出來，請問是哪個才正確呢?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.62.164.225
1F：推 anfranion:應該是對的，spanning tree的定義還有任兩點之間 02/08 18:25
2F：→ anfranion:要有唯一的path(在無向時) 02/08 18:25
3F：→ anfranion:有向時是root到該點有唯一path 02/08 18:25
4F：→ stator:謝謝a大的解說 02/08 21:15