[問題] is spanning tree wintercobra PTT批踢踢實業坊

作者: wintercobra (wintercobra) 2012-04-29 23:01:50

請問一下
在測試 is_spanning_tree 這個功能時
會假定「給入的兩個 graph 原本是完全一樣的，只是少了一些邊」嗎？
也就是說，會不會給個完全不同的 graph ，或是偷拿走一些頂點，需要額外檢驗呢？
謝謝

作者: Usoul 2012-04-30 11:50:00

這一題可以說是獨立題，跟read_graph中存入的圖沒有關係is_spanning_tree不用將input dot file存起來，只需要檢查後輸出 Yes/No 即可

作者: wintercobra (wintercobra) 2012-04-30 13:56:00

瞭解，謝謝還有一個問題是，is_spanning_tree輸出YES或NO是輸出到stdout嗎？

作者: Usoul 2012-04-30 23:29:00

是的。

作者: photonzero (邪心魔佛) 2012-05-02 18:21:00

所以說就是檢查input dot file是否是tree嗎

作者: Usoul 2012-05-02 19:27:00

是

作者: vincere (vin) 2012-05-05 10:19:00

想請問一下因為這篇關於is_spanning_tree的功能好像跟上課老師講的有些不同記得老師好像說是要跟read進來的graph比所以想要確定一下不知我是否有誤會意思？

作者: Usoul 2012-05-05 15:36:00

老師說明的是對的，在此更正一下：is_spanning_tree 要檢查是否是原圖的 spanning tree，之後再輸出 Yes/No。所以不算是獨立題所以除了檢查是樹之外，還要檢查點都存在，且邊是子集之前沒有想清楚，所以回答得有問題，對不起 QQ"

作者: cjshine (花) 2012-05-05 17:02:00

請問一下檢查邊的時候需要檢查它的label嗎?

繼續閱讀