Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=426453&view=findpost&p=3898172 Thu, 21 Dec 2023 04:38:43 +0000 Минимальное остовное дерево (2ое минимальное) https://forum.sources.ru/index.php?showtopic=426453&view=findpost&p=3898172
Массив из пар вершин?]]> Квант Алгоритмы https://forum.sources.ru/index.php?showtopic=426453&view=findpost&p=3862315 Fri, 01 Apr 2022 08:24:10 +0000 Минимальное остовное дерево (2ое минимальное) https://forum.sources.ru/index.php?showtopic=426453&view=findpost&p=3862315 Вот тут человек рассматривает подход, как можно перебор для этой задачи организовать]]> OpenGL Алгоритмы https://forum.sources.ru/index.php?showtopic=426453&view=findpost&p=3862311 Fri, 01 Apr 2022 07:49:55 +0000 Минимальное остовное дерево (2ое минимальное) https://forum.sources.ru/index.php?showtopic=426453&view=findpost&p=3862311 Цитата FasterHarder @
факториальная сложность вроде бы

Ну если О(), может быть, и факториальная, в чём я лично сомневаюсь, то о() точно степенная.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=426453&view=findpost&p=3862289 Thu, 31 Mar 2022 14:56:34 +0000 Минимальное остовное дерево (2ое минимальное) https://forum.sources.ru/index.php?showtopic=426453&view=findpost&p=3862289 Akina, понял, спс, значит полный перебор получается) + факториальная сложность вроде бы]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=426453&view=findpost&p=3862251 Thu, 31 Mar 2022 07:16:43 +0000 Минимальное остовное дерево (2ое минимальное) https://forum.sources.ru/index.php?showtopic=426453&view=findpost&p=3862251 А так, если строить не N-ое, а второе, то вроде бы даже не сильно сложно в плане реализации - цикл по рёбрам, и в цикле запускаем обычное построение минимального остова любым алгоритмом, но не с нуля, а с ситуации "уже есть текущее ребро". Среди всех построенных деревьев выбираешь второе.]]> OpenGL Алгоритмы https://forum.sources.ru/index.php?showtopic=426453&view=findpost&p=3862244 Thu, 31 Mar 2022 06:05:28 +0000 Минимальное остовное дерево (2ое минимальное) https://forum.sources.ru/index.php?showtopic=426453&view=findpost&p=3862244
А ПП, во всяком случае, гарантирует, что результат будет получен.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=426453&view=findpost&p=3862238 Wed, 30 Mar 2022 22:59:04 +0000 Минимальное остовное дерево (2ое минимальное) https://forum.sources.ru/index.php?showtopic=426453&view=findpost&p=3862238
Есть связный взвешенный граф (не важно какой: ор или неор).
Используя алгоритм Прима или Крускала можно найти минимальный остов.
А как найти 2ой по минимальности остов в частном случае или Nый по минимальности в общем случае?

Или это ТОЛЬКО полный перебор?]]> FasterHarder Алгоритмы