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

[cakeboy ()]

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
推 juan19283746:從每個點做BFS?
推 christianSK:我有google過diameter這個問題
→ christianSK:我記得一個解法是找graph的中心點
→ christianSK:像圓一樣的向外擴張來找最長diameter
推 babygoat:任取一點做bfs找最遠點 再從這個點再做一次bfs找最遠點
→ babygoat:取其距離即為diameter
→ cakeboy:是每一點都要做嗎
推 babygoat:一個點就好了