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

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

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

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

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

Ответ 1

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

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

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

Ответ 2

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

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

Ответ 3

Рональд Ривест имеет приятную реализацию в Python, mst.py

Ответ 4

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

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