Изменения

Перейти к: навигация, поиск

Алгоритмы на деревьях

4 байта добавлено, 20:53, 11 декабря 2013
Нет описания правки
{'''Обоснование корректности:''' 
Будем пользоваться свойством,что в любом дереве >= 2 висячих вершин(степерь у них = 1)
Таким образом мы доказали, что нам нужно взять наиглубочайшую вершину t после первого bfs, очевидно что ей в пару надо сапоставить вершину p , что dist(t, p) - max . Очевидно, что проблема решается запуском bfs из t.
}
'''Оценка производительности:'''
Все операции кроме bfs - О(1)
BFS работает линейное время,запускаем мы его 2 раза.Получаем O(V+E)
Анонимный участник

Навигация