Привет всем! Собственно я столкнулся с задачей на нахождение центров дерева (Дерево — связный неориентированный граф без циклов). В интернете толком не нашел понятного мне определения центра дерева. Прошу, объясните мне что такое центр дерева? И какой алгоритм нахождения центров?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
Вероятно имеется ввиду вершина, максимальное расстояние до другой вершины от которой минимально.[Таких вершин может быть несколько]
А алгоритм нахождения какой будет? Тут надо использовать поиск в ширину?
центр дерева это вершина максимально удаленная от других вершин. в дереве центр это либо одна вершина либо две, находящаяся(находящиеся) в середине пути между двумя самыми удаленными вершинами. чтобы найти две самых удаленых вершины в дереве (за расстояние между соседними вершинами считаем 1) можно использовать два поиска в ширину (для дерева можно и DFS). сначала найдем от любой вершины x самую удаленную от неё вершину y, затем найдем вершину z, самую удаленную от y. путь из y в z — это один из самых больший путей в графе.
Спасибо! Теперь стало понятно!
Вообще-то, это не будет один из самых больших путей.
Вот, например:
Если начать из левой вершины, то придём в правую, а потом — снова в левую. Тогда как самый длинный путь — между верхней и нижней.
Ваш граф не дерево. "центр дерева это..."
Согласен, что не для дерева это не работает. А как найти самый длинный путь для произвольного графа? (Веса единичные)
не знаю, алгоритмом Флойда, например. А Вы можете доказать, что такой алгоритм работает для дерева?
Да, это не очень сложно доказывается. A — начальная вершина, B — самая удаленная от A, C — самая удаленная от B. 1: Максимальный путь и путь от B к C имеют общую вершину. Если нет общей вершины, то есть путь длиннее масимального или один из концов максимального пути удален от B дальше чем C, что невозможно исходя из выбора точки C. Потом рисуем крестик, обозначаем точки и видим что это максимальный путь по любому :) Ночь сейчас, посмотри на рисунок там все вроде понятно, лениво расписывать все случаи сейчас.
А по поводу Флойда пожалуйста подробнее, кое-где на форумах говорят что задача поиска наидлиннейшего пути NP.
Казалось бы, она не проще Гамильнонова пути, нет?
Так ведь нам нужен не самый длинны путь, а самое большое расстояние между вершинами. То есть, самый длинный кратчайший путь. И, казалось бы, узнав расстояние между всеми парами вершин алгоритмом Флойда, мы сможем выбрать из них наибольшее.
Сегодня узнал простой вариант решения этой проблемы: можно сделать поиск в ширину, начав с листьев дерева. То есть сначала найти листья (вершины с degree == 1) за линейное время, добавить их в очередь и запустить BFS. Последняя достигнутая вершина будет центром (или одной из центральных). http://stackoverflow.com/questions/4020122/finding-center-of-the-tree
Чтобы найти все центры, нужно по ходу BFS сохранять высоту каждой пройденной вершины (для листьев — 0, потом 1, и т.д.), все вершины с максимальной высотой будут центрами.
Не уверен, но по-моему в дереве не может быть больше двух центров.
UPD: упс, извините, алгоритм неправильный, читайте далее.
Вранье же:
Вы быстро достигнете центра этого дерева, но в очередь вы его последним точно не добавите.
На онсайте открытого кубка 2011-го года была задача, которую я так и решал, просто алгоритм не описан во всех подробностях, а дана лишь идея. Не помню на что была задача, то ли полиморфизм двух деревьев определить, то ли посчитать чего-то хитрое. Понятно что мы не можем обрезать 6 близких к центру листьев до тех пор, пока длинные щупальца не пообрезаются до длины 1. Это похоже на бфс, но нужны дополнительные телодвижения чтобы удалять правильно. Занумеруем 9 центральных вершин слева направо снизу вверх (как клавиши цифр на телефоне) чтобы понятнее было дальнейшее объяснение. У каждой вершины есть счетчик живых соседей. Когда счетчик живых соседей становится равным единице, вершину следует убить, а также "похоронить" её убитых соседей, пометив их все порядковым номером текущего раунда убийств. В нулевом раунде убьются две крайние вершины щупалец и вершины 1, 2, 3, 7, 8, 9. В первом раунде убъются вторая слева и вторая справа вершины, края щупалец будет погребены, и им назначется число 1. ... в 6-ом раунде убъем вершины 4 и 6, а вершины 1, 2, 3, 7, 8, 9 и еще две по краям будут похоронены.
Avitella, Alias, спасибо, вы абсолютно правы. Не понимаю, почему вас заминусовали, а меня — наоборот. Наверное, потому, что мой ошибочный вариант звучит проще :)
Извините, кого ввёл в заблуждение. По ссылке на стековерфлоу было правильное объяснение, но я его исковеркал, пытаясь упростить. На самом деле нужно запустить не BFS из листьев, а удаление листьев. И повторять удаление листьев до тех пор, пока не останется одна/две вершины. Это и будет центром.
Четыре вершины, соединенные последовательно. Вот вам дерево с двумя центрами.
В дереве однозначно не может быть больше двух центров, я могу привести доказательство, если хотите. Это прямо вытекает из того, что это середина (или обе середины) самого длинного пути дерева, это я тоже могу доказать, если интересно.