Вся минимальная реализация связующих деревьев
Я искал реализацию (я пользуюсь networkx библиотекой.), который найдет все минимальные связующие деревья (MST) неориентированного взвешенного графика.
Я могу только найти реализации для Алгоритма Kruskal и Алгоритма Prim, оба из которых только возвратят единственный MST.
Я видел бумаги, которые решают эту проблему (такую как Представление всех минимальных связующих деревьев с приложениями к подсчету и поколению), но моя голова имеет тенденцию взрываться некоторым образом посредством попытки думать, как перевести его для кодирования.
На самом деле я не смог найти реализацию на любом языке!
1 ответ
Не знаю, является ли это решением, но это решение (это графовая версия перебора, я бы сказал):
- Найдите MST графа, используя алгоритм Крускала или Прима. Это должно быть O(E log V).
- Сгенерируйте все прямые деревья. Это может быть сделано за
O(Elog(V) + V + n) для n = количество прямых деревьев, как я понял из 2 минут гугления, возможно, можно улучшить. - Отфильтруйте список, сгенерированный на шаге #2, по весу дерева, равному весу MST. Это должно быть O(n) для n как количество деревьев, сгенерированных на шаге #2.
Примечание: Делайте это лениво! Генерация всех возможных деревьев и последующая фильтрация результатов займет O(V^2) памяти, а полиномиальные требования к пространству - зло. Сгенерируйте дерево, проверьте его вес, если это MST, добавьте его в список результатов, если нет - отбросьте его.
Общая временная сложность: O(Elog(V) + V + n) для G(V,E) с n охватывающими деревьями