[理工] [DS] 99-清大資工所

看板Grad-ProbAsk作者時間15年前 (2011/01/22 22:16), 編輯推噓4(404)
留言8則, 4人參與, 最新討論串1/1
http://www.lib.nthu.edu.tw/library/department/ref/exam/eecs/cs/99/1901.pdf 請問第12題的diameter要怎麼求呢? 雖然他有說明diameter定義 但是例如:p q兩點 找最長路徑的話 是p->q 還是要每個邊都走過一次呢? 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.231.170.230

01/22 22:45, , 1F
從每個點做BFS?
01/22 22:45, 1F

01/22 22:59, , 2F
我有google過diameter這個問題
01/22 22:59, 2F

01/22 22:59, , 3F
我記得一個解法是找graph的中心點
01/22 22:59, 3F

01/22 23:00, , 4F
像圓一樣的向外擴張來找最長diameter
01/22 23:00, 4F

01/23 00:31, , 5F
任取一點做bfs找最遠點 再從這個點再做一次bfs找最遠點
01/23 00:31, 5F

01/23 00:32, , 6F
取其距離即為diameter
01/23 00:32, 6F

01/23 00:50, , 7F
是每一點都要做嗎
01/23 00:50, 7F

01/24 01:03, , 8F
一個點就好了
01/24 01:03, 8F
文章代碼(AID): #1DEkQp-3 (Grad-ProbAsk)