[理工] [演算] graph algotithm

看板Grad-ProbAsk作者metalalive (想玩音樂)時間12年前 (2012/01/31 17:27)推噓9(9推 0噓 11→)

留言20則, 5人參與討論串1/1

http://www.lib.nthu.edu.tw/library/department/ref/exam/eecs/cs/99/1901.pdf 請教最後一題 a小題題意 , minimum diameter 這邊的意思是? Sorry , diameter 的意思我了解但是不知到這邊要求出 "minimum" diameter 我對a小題的理解,如果沒錯的話,是不是指... 我要怎麼找 spanning tree 才可以找到 graph 的某個 spanning tree 其 diameter 為最小不過 , 這好像是 b 小題要我們做的事 :P 還有b小提的做法 3Q -- No time to pray.... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.128.126.145

推

wheels

01/31 17:36, , 1^F

01/31 17:36, 1^F

→

wheels

01/31 17:36, , 2^F

01/31 17:36, 2^F

推

onlyeric23

01/31 19:00, , 3^F

01/31 19:00, 3^F

謝謝提醒@O@

推

wheels

01/31 19:59, , 4^F

01/31 19:59, 4^F

→

metalalive

01/31 22:33, , 5^F

01/31 22:33, 5^F

→

metalalive

01/31 22:34, , 6^F

01/31 22:34, 6^F

如果我沒弄錯 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

01/31 23:07, , 7^F

01/31 23:07, 7^F

→

wheels

01/31 23:07, , 8^F

01/31 23:07, 8^F

→

wheels

01/31 23:08, , 9^F

01/31 23:08, 9^F