Самый быстрый алгоритм минимального связующего дерева

Question

http://en.wikipedia.org/wiki/Minimum_spanning_tree

Я собираюсь сравнить мой алгоритм минимального связующего дерева с лучшим из лучших.Кто-нибудь знает, где я могу найти реализацию этих алгоритмов на C ++?Я глотал и гуглил и ничего не нашел.Если эти алгоритмы являются лучшими, наверняка где-то должна быть реализация на C ++?

Самый быстрый алгоритм минимального связующего дерева на сегодняшний день был разработан Дэвидом Каргером, Филиппом Кляйном и Робертом Тарьяном, которые нашли линейныйрандомизированный по времени алгоритм, основанный на комбинации алгоритма Боровки и алгоритма обратного удаления. [2] [3]Самый быстрый нерандомизированный алгоритм Бернарда Шазеля основан на мягкой куче, очереди с приблизительным приоритетом. [4] [5]Время его выполнения составляет O (m α (m, n)), где m - число ребер, n - число вершин, а α - классическая функциональная обратная функция Аккермана.Функция α растет крайне медленно, поэтому для всех практических целей ее можно считать постоянной не более 4;таким образом, алгоритм Шазеля занимает очень близко к линейному времени.Если веса ребер являются целыми числами с ограниченной длиной в битах, то известны детерминированные алгоритмы с линейным временем выполнения. [6]Существует ли детерминированный алгоритм с линейным временем выполнения для общих весов, все еще остается открытым вопросом.Тем не менее, Сет Пети и Виджая Рамачандран нашли доказуемый оптимальный детерминистический алгоритм минимального остовного дерева, вычислительная сложность которого неизвестна. [7]

Я уже тестировал алгоритмы графов Boost C ++.

Answer 1

Когда на странице Википедии написано «самый быстрый алгоритм минимального связующего дерева», они имеют в виду алгоритм с наименьшими асимптотическими границами - в данном случае O (m α (m, n)), с m, n и α определяется как в вставленной вами цитате. Проще говоря, это означает, что для очень больших входных значений количество времени всегда будет ограничено C * m * α (m, n) для некоторого значения C. Но обратите внимание, что C может быть очень большим - т.е. этот алгоритм может быть медленнее других при применении к меньшим входным значениям, даже если он работает быстрее других при очень больших входных значениях.

При сравнении асимптотических границ двух алгоритмов нет «проверки», чтобы увидеть, какой из них быстрее, - вы просто докажете асимптотические границы каждого алгоритма и посмотрите, какой из них ниже. («Асимптотика» относится к поведению, когда размер входных данных уходит в бесконечность, и трудно выполнять тесты с входными значениями бесконечного размера.)

Но учтите, что в некоторых случаях вы должны не использовать асимптотически быстрый алгоритм. Если буква «С» очень велика, вам лучше использовать более простой алгоритм для меньших значений данных.

Я предполагаю, что ваш алгоритм может улучшиться на C, но не на асимптотических границах. Но если я ошибаюсь, отправьте это в ACM!

Подробнее см .: http://en.wikipedia.org/wiki/Big_O_notation

Answer 2

«О сортировке, кучах и минимальных остовах», Гонсало Наварро и Родриго Паредес

представляет некоторые «лучшие из лучших» измерений в ядре и внешней памяти, а также даетссылки на более старые реализации.

Они сообщают о количестве операций ввода-вывода и времени процессора в зависимости от размера графика и хорошо описывают их тестовые примеры, поэтому в принципе вы можете выполнять тесты и сравнивать их с опубликованными графиками.Вы можете использовать их ссылку на Prim2 (код Питера Сандерса, который делает многие из своих быстрых кодов доступными бесплатно) для калибровки ваших собственных измерений.