推 wheels:a.tree中任兩點之最長距離。 01/31 17:36
→ wheels:b.沒有限制複雜度，暴力法找出全部的ST再找MD最小者。 01/31 17:36
推 onlyeric23:b可以做bfs 01/31 19:00
謝謝提醒@O@
推 wheels:可以告知bfs的詳細作法嗎？這題我也是琢磨了很久沒有結果。 01/31 19:59
→ metalalive:只能用暴力法喔@@ , 好吧謝謝 01/31 22:33
→ metalalive:我看錯了,我以為1f說a小題只能要暴力法,sorry :P 01/31 22:34
如果我沒弄錯 minimum diameter 的意思的話
B小題的作法大概是
令 G=(V,E)
1.用暴力法找出g的所有 spanning tree
(可以請教onlyeric23的意思是可以用BFS抓到所有spanning tree?)
2.再分別對這些spanning tree 抓出它的 diameter
每個spanning tree 執行2次 BFS 就可以抓到 diameter 了
所以會產生 |V| 個 diameter
3.最後再抓出哪個 diameter 為最小
這樣想不知道有沒有盲點 @O@
3Q
※ 編輯: metalalive 來自: 124.8.82.148 (01/31 22:52)
※ 編輯: metalalive 來自: 124.8.82.148 (01/31 22:55)
推 wheels:是這樣沒錯，但是我以為b可以設計出只用BFS應用抓到某個ST 01/31 23:07
→ wheels:是我會錯意嗎= =? 01/31 23:07
→ wheels:因為我試過由最大degree下手，由某點連結最多點之degree和 01/31 23:08
→ wheels:為最大下手等方式都無法成功，最後只能用暴力法抓全部ST。 01/31 23:09
推 bbhands:先找出graph的center，再以center為起點找BFS tree即可 02/01 00:01
→ bbhands:至於center的找法，就完全照定義計算 02/01 00:01
推 bbhands:抱歉 center還不夠 必須是absolute-1-center才行 02/01 00:23
→ bbhands:可搜尋MDST(Minimum Diameter Spanning Tree)Hassin&Tamir 02/01 00:24
→ metalalive:sorry 我有喵了 absolute-1-center 的說明,看不懂@@ 02/01 01:37
→ metalalive:不知道它的概念是什麼呢? 謝謝@@ 02/01 01:37
推 bbhands:就是把center的定義放寬到允許在邊上的某處(不見得是頂點) 02/01 02:13
推 bbhands:以本題來說absolute 1-center可能是某頂點或是某邊的中點 02/01 02:16
推 bbhands:例如P_4(長度3的path)，離心率最小的地方在中間邊的中點 02/01 02:23