Comments 17
На практике же его используют чаще для решения комбинаторных задач.
Можно с этого места поподробнее?
Могу предложить такой пример: равновероятно сгенерировать случайное дерево. Кожд Прюфера кажется самым простым решением, как без него добиться равновероятности деревьев — непонятно.
Или дерево определенного размера? Дерево с ограничением на размер сверху? Остовное дерево для заданного графа? k-ичное дерево?
Это все очень разные задачи, уточните пожалуйста, какую именно вы имели в виду.
А можно для тех кто "не в теме", что значит " добиться равновероятности дерева"?
Вот есть множество всех деревьев на N вершинах, их конечно, а точнее — N^{N-2} по теореме Кэли. Давайте их как-нибудь занумеруем, потом выберем случайное число от 1 до N^{N-2} равновероятно (т.е. каждое число выбирается с одинаковой вероятностью), возьмём дерево с таким номером.
В шаге про завершение алгоритма опечатка, там нет никакой минимальной вершины в не в коде. Тем более ей не может быть 1.
Основной вопрос, если уж алгоритм обсуждать, а за какую сложность можно этот код построить? А как долго приведенный алгоритм восстановления дерева работает? Можно ли его за линейную сложность реализовать?
Код Прюфера