Алгоритмы на деревьях — различия между версиями
Строка 1: | Строка 1: | ||
+ | __TOC__ | ||
+ | == Определение == | ||
+ | |||
'''Диаметр дерева''' - максимальная длина кратчайшего пути между любыми двумя вершинами. | '''Диаметр дерева''' - максимальная длина кратчайшего пути между любыми двумя вершинами. | ||
Алгоритм в этой статье находит диаметр в дереве,причём очень простой реализацией и низким временем работы. | Алгоритм в этой статье находит диаметр в дереве,причём очень простой реализацией и низким временем работы. |
Версия 18:04, 17 декабря 2013
Определение
Диаметр дерева - максимальная длина кратчайшего пути между любыми двумя вершинами. Алгоритм в этой статье находит диаметр в дереве,причём очень простой реализацией и низким временем работы.
Алгоритм
Возьмём любую вершину
и найдём расстояния до всех других вершин.d = min{
, } dist( )Возьмём вершину
такую,что d[u] >= d[t] для любого t.Снова найдём расстояние от до всех остальных вершин.Самое большое расстояние - диаметр дерева. Расстояние до остальных вершин удобно искать алгоритмом BFS.Реализация
int diameterTree(graph g) { v = u = w = 0; bfs(g,v); // заполняет массив d[n] кратчайшими расстояниями до всех вершин. for(i = 0; i < n; i++) if (d[i] > d[u]) u = i; bfs(g,u); for(i = 0; i < n; i++) if (d[i] > d[w]) w = i; return d[w]; }
Обоснование корректности
Будем пользоваться свойством,что в любом дереве >= 2 листов(имеют степень один).
Теорема: |
Искомое расстояние - есть расстояние между двумя листами. |
Доказательство: |
Пусть нет, пусть искомое расстояние - есть расстояние между вершинами | где - не является листом. Т.к. b не является листом, то значит её степень 1 => из неё существует ребро в непосещенную вершину (дважды посетить вершину мы не можем). Лемма доказана.
Запустив BFS от произвольной вершины. Мы получим дерево BFS.
Теорема: |
В дереве BFS не существует ребер между вершинами из разных поддеревьев некоторого из общего предка. |
Доказательство: |
Такое же как у дерева dfs. |
Мы свели задачу к нахождению вершины
, такой, что сумма глубин поддеревьев максимальна.Докажем, что одно из искомых поддеревьев содержит самый глубокий лист. Пусть нет, тогда взяв расстояние от
до глубочайшего листа мы можем улучшить ответ.Таким образом мы доказали, что нам нужно взять вершину
с наибольшей глубиной после первого bfs, очевидно что ей в пару надо сопоставить вершину , что dist(u, w) - . Очевидно, что проблема решается запуском bfs из .
Оценка производительности:
Все операции кроме bfs - О(1). BFS работает линейное время,запускаем мы его 2 раза.Получаем O(V+E).