Минимальное остовное дерево (2ое минимальное)

[FasterHarder]

Всем хай! Сходу к делу!

Есть связный взвешенный граф (не важно какой: ор или неор).
Используя алгоритм Прима или Крускала можно найти минимальный остов.
А как найти 2ой по минимальности остов в частном случае или Nый по минимальности в общем случае?

Или это ТОЛЬКО полный перебор?

[Akina]

Убеждён, что стандартного алгоритма не существует. Более того, мне даже не известно о существовании алгоритма для построения всех возможных остовов графа (хотя это по сути обычная комбинаторная задача с кучей возможных алгоритмов её решения, но я не видел их применения или даже упоминания о возможности их применения для именно построения всех возможных остовов). Да что алгоритм - я и самой задачи-то такой не видел.

А ПП, во всяком случае, гарантирует, что результат будет получен.

[OpenGL]

Что вообще такое "второй по минимальности остов"? Если у нас полный граф, и все его рёбра одинакового веса, то второго дерева не существует, или второе дерево тоже минимальным является?
А так, если строить не N-ое, а второе, то вроде бы даже не сильно сложно в плане реализации - цикл по рёбрам, и в цикле запускаем обычное построение минимального остова любым алгоритмом, но не с нуля, а с ситуации "уже есть текущее ребро". Среди всех построенных деревьев выбираешь второе.

[FasterHarder]

Akina, понял, спс, значит полный перебор получается) + факториальная сложность вроде бы

[Akina]

Цитата FasterHarder @ 31.03.22, 14:56

факториальная сложность вроде бы

Ну если О(), может быть, и факториальная, в чём я лично сомневаюсь, то о() точно степенная.

[OpenGL]

Вот тут человек рассматривает подход, как можно перебор для этой задачи организовать

[Квант]

А как результат нахождения основного дерева обычно представляется?

Массив из пар вершин?