Все минимальные реализации связующих деревьев

Question

Я искал реализацию (я использую библиотеку networkx ), которая найдет все минимальные остовные деревья (MST) неориентированного взвешенного графа.

Я могу найти только реализации для алгоритма Крускала и алгоритма Прима, оба из которых будут возвращать только один MST.

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

На самом деле я не смог найти реализацию ни на одном языке!

Answer 1

Я не знаю, является ли это решением , но это решение (я бы сказал, это графическая версия грубой силы):

1. Найдите MST графа, используя алгоритм Крускала или Прима. Это должно быть O (E log V).
2. Генерация всех связующих деревьев. Это можно сделать в O(Elog(V) + V + n) for n = number of spanning trees, как я понимаю из Google за 2 минуты, можно улучшить.
3. Отфильтруйте список, сгенерированный на шаге 2, по весу дерева, равному весу MST. Это должно быть O (n) для n как количество деревьев, сгенерированных на шаге № 2.

Примечание: делайте это лениво! Генерация всех возможных деревьев и последующая фильтрация результатов потребуют O (V ^ 2) памяти, а требования к полиномиальному пространству - зло .
Общая сложность времени: O(Elog(V) + V + n) for G(V,E) with n spanning trees

Answer 2

Рубис дает хороший общий ответ. Но написание эффективного кода для генерации всех связующих деревьев графа является сложной задачей.

На полпути вниз на этой странице , примерно в декабре 2003 года вы найдете CWEB-реализацию алгоритма Кнута, который находит все остовные деревья данного графа.

Answer 3

У Рональда Ривеста хорошая реализация на Python, mst.py

Answer 4

Вы можете найти идею в работе Sorensen and Janssens (2005) .

Идея состоит в том, чтобы генерировать ST в возрастающем порядке, и как только вы получите большее значение ST, остановите перечисление.