Поиск центра графа |
Поиск центра графа |
Tony |
2.01.2010 23:18
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 17 Пол: Мужской Репутация: 1 |
Здравствуйте.
Собственно задача: Имеется сильно связный неориентированный невзвешенный граф. Требуется найти такую вершину (центр), чтобы кратчайшие расстояния от нее до всех остальных вершин графа были, по-возможности, минимальны.(по-моему не совсем корректно, поэтому скажу иначе: поиск в ширину, пущенный от нее, должен сделать минимальное число "волн"). Естественно, решение за O(n^2) очевидно (просто серия из n поисков в ширину), но при этом время работы алгоритма слишком велико. Собственно, был бы рад любым идеям по реализации данного алгоритма . ЗЫ Из собственных мыслей: 1.) Взять произвольную вершину. Пустив bfs из нее, найти наиболее удаленную от нее вершину ( пусть она будет называться L ). Пустив bfs от L, найти наиболее удаленную от нее вершину ( R ). Пустить одноременно два bfs'а от L и R и ждать их пересечения. Центр, имхо, будет лежать где-то в множестве вершин, вошедших в это пересечение. (но опять - таки их слишком много) 2.) Попытаться использовать данные предыдущих поисков. Но эта идея по-моему бесперспективна... |
Tony |
5.01.2010 23:39
Сообщение
#2
|
Новичок Группа: Пользователи Сообщений: 17 Пол: Мужской Репутация: 1 |
Цитата Во-первых, Дейкстра - он. И алгоритм, кстати, - тоже. Да и в придумывании велосипедов (особенно для олимпиады) ничего плохоого нет. Я, например, и придумал и написал несколько реализаций "Дейкстры" до того, как узнал, что этот алгоритм, оказывается, имеет имя собственное (причем, что самое обидное - не мое smile.gif. Возможно, алгоритм Дейкстры не самый удачный пример)) Ну да ладно... Цитата Если это задача с реальной олимпиады, в которой ты в данный момент участвуешь, то думай сам. Если это с какой-то давно прошедшей, то тогда да, попробуем помочь. О'кей, буду думать) |
Текстовая версия | 18.05.2024 19:30 |