作者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