Да, это домашнее задание. Мне было интересно, сможет ли кто-нибудь объяснить процесс алгоритма Соллина (или Borůvka's) для определения минимального остовного дерева. Также, если бы вы могли объяснить, как определить количество итераций в худшем случае, это было бы здорово.Алгоритм минимального спаривания дерева Соллина
На верхнем уровне, алгоритм работает следующим образом:
Худший случай с точки зрения итераций заключается в том, что вы всегда объединяете пары деревьев. В этом случае количество деревьев, которые у вас есть, будет уменьшаться на половину на каждой итерации, поэтому число итераций логарифмическое число узлов.
Также обратите внимание на то, дерево A. (Это может произойти только в том случае, если все три выбранные ребра имеют одинаковый вес. Трюк состоит в том, чтобы иметь произвольный, но фиксированный тай-брейкер, как фиксированный порядок ребер.)
Итак, это моя спина обзор-обзор-карты.
Итак, в случае дерева узлов 100 наихудший случай будет принимать log2 (100) или 7 итераций? – Brendan
@Brendan: Да, звучит правильно. Я признаю, что меня не интересуют постоянные факторы, которые O() - Обозначение скрывается от вас, но я не думаю, что здесь есть. –
Спасибо. Я думаю, что между вашим объяснением и моим исследованием я правильно использую этот алгоритм. – Brendan
Я использую терминологию непрофессионала.
Ваш остов с минимальным весом будет сформирован
http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm? Если что-то конкретное вы не понимаете, спросите об этом. В противном случае прочитайте учебник, википедию, источники в Википедии и т. Д. – nmichaels
Не мог бы кто-нибудь объяснить, почему этот человек Гарет Рис продолжает удалять тег «дискретная математика» из этого вопроса и почему он проголосовали? Я не злюсь; Я просто не понимаю, как работает этот сайт, поскольку я новичок. Этот вопрос кажется законным вопросом на этом сайте, и я считаю, что он подпадает под дискретную математику, особенно из-за того, что эта домашняя работа происходит из курса под названием «Дискретная математика». – Brendan
Дискретная математика - это набор тем, посвященных целям (в отличие от непрерывной математики). Итак, последовательности, рекуррентности, суммирование, производящие функции, биномы, конечное исчисление и т. Д. Алгоритмы предоставляют множество * примеров * для дискретных математических вычислений, но это не значит, что все вопросы об алгоритмах - это вопросы о дискретных математиках. Что касается downvotes, я не знаю. (Я думаю, что ваш вопрос в порядке, просто неверно отмечен.) –