作者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