作者cakeboy ()
看板Grad-ProbAsk
標題[理工] [DS] 99-清大資工所
時間Sat Jan 22 22:16:16 2011
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
1F：推 juan19283746:從每個點做BFS? 01/22 22:45
2F：推 christianSK:我有google過diameter這個問題 01/22 22:59
3F：→ christianSK:我記得一個解法是找graph的中心點 01/22 22:59
4F：→ christianSK:像圓一樣的向外擴張來找最長diameter 01/22 23:00
5F：推 babygoat:任取一點做bfs找最遠點 再從這個點再做一次bfs找最遠點 01/23 00:31
6F：→ babygoat:取其距離即為diameter 01/23 00:32
7F：→ cakeboy:是每一點都要做嗎 01/23 00:50
8F：推 babygoat:一個點就好了 01/24 01:03