Вы можете сделать это за O(V²). Сначала вычислите MST, используя алгоритм Прима (можно выполнить за O(V² )).

Вычислите max[u, v] = the cost of the maximum cost edge on the (unique) path from u to v in the MST. Можно сделать за O(V²).

Найдите ребро (u, v), НЕ являющееся частью MST, которое минимизирует abs(max[u, v] - weight(u, v)). Можно сделать за O(E) == O(V²).

Верните MST' = MST - {the edge that has max[u, v] weight} + {(u, v)}, что даст вам второй лучший MST.

Вот ссылка на псевдокод и более подробные пояснения.

Рассмотрим этот случай:

------100----
|           |
A--1--B--3--C
      |     |
      |     3
      |     |
      2-----D

MST состоит из A-B-D-C (стоимость 6). Вторая минимальная стоимость — A-B-C-D (стоимость 7). Если вы удалите ребро с наименьшей стоимостью, вместо этого вы получите A-C-B-D (стоимостью 105).

Так что ваша идея не сработает. Хотя у меня нет идеи лучше...

Вы можете сделать это - попробуйте удалить ребра MST по одному из графа и запустить MST, взяв из него min. Итак, это похоже на ваше, за исключением итеративного:

1. Используйте Kruskals, чтобы найти MST.
2. For each edge in MST:
   1. Remove edge from graph
   2. Рассчитать MST' на MST
   3. Следите за наименьшим MST
   4. Добавить ребро обратно к графику
3. Возвращает наименьший MST.

Это похоже на ответ Ларри.

Найдя MST,

Для каждого new_edge = не ребро в MST

1. Добавьте new_edge в MST.
2. Найдите цикл, который образовался.
3. Найдите ребро с максимальным весом в цикле, которое не является добавленным вами ребром не-MST.
4. Запишите увеличение веса как W_Inc = w(new_edge) - w(max_weight_edge_in_cycle).
5. If W_Inc < Min_W_Inc_Seen_So_Far Then
   • Min_W_Inc_Seen_So_Far = W_Inc
   • edge_to_add = новое_крае
   • edge_to_remove = max_weight_edge_in_cycle

Решение по следующей ссылке.
http://web.mit.edu/6.263/www/quiz1-f05-sol.pdf

небольшое редактирование вашего алгоритма.

    Use kruskals to find lowest MST.
    for all edges i of MST
        Delete edge i of the MST.
        Run kruskals again on the entire graph.
        loss=cost new edge introduced - cost of edge i
    return MST for which loss is minimum

Вот алгоритм, который вычисляет 2-е минимальное остовное дерево за O (n ^ 2)

1. Сначала найдите минимальное остовное дерево (T). Это займет O (n ^ 2) без использования кучи.
2. Повторите для каждого ребра e в T. =O(n^2)

3. Предположим, что текущее ребро дерева равно e. Это ребро дерева разделит дерево на два дерева, скажем, T1 и T-T1. e=(u,v) где u находится в T1, а v находится в T-T1. = О (п ^ 2)

   Повторите для каждой вершины v в T-T1. = О (п ^ 2)

   Выберите ребро e'=(u,v) для всех v в T-T1 и e' в G (исходный граф), и оно минимально

4. Рассчитайте массу новообразованного дерева. Скажем W=weight(T)-weight(e)+weight(e')

5. Выберите тот T1, который имеет минимальный вес

Ваш подход не сработает, так как может случиться так, что мин. весовое ребро в MST является мостом (только одно ребро, соединяющее 2 части графа), поэтому удаление этого ребра из набора приведет к 2 новым MST по сравнению с одним MST.

_{на основе ответа @IVlad}

Подробное объяснение алгоритма O(V² log V)

• Найдите минимальное остовное дерево (MST), используя алгоритм Крускала (или Прима), сохраните его общий вес и для каждого узла в MST сохраните его соседей по дереву (т.е. родителя и всех потомков) -> O(V² log V)
• Вычислите максимальный вес ребра между любыми двумя вершинами в минимальном остовном дереве. Начиная с каждой вершины в MST, пройдитесь по всему дереву поиском в глубину или в ширину, используя списки соседей узлов дерева, вычисленные ранее, и сохраните максимальный вес ребра, обнаруженный до сих пор в каждой новой посещенной вершине. -› O(V²)
• Найдите второе минимальное остовное дерево и его общий вес. Для каждого ребра, не принадлежащего исходному MST, попробуйте отсоединить две вершины, которые оно соединяет, удалив ребро дерева с максимальным весом между двумя вершинами, а затем повторно соединив их с рассматриваемой в данный момент вершиной (примечание: MST должен быть восстановлен до исходное состояние после каждой итерации). Общий вес можно рассчитать, вычитая вес удаленного ребра и добавляя вес добавленного. Храните минимум из полученных весов.

Для практики вы можете попробовать соревновательную задачу по программированию UVa 10600 - ACM Contest and Blackout, который включает в себя поиск второго минимального остовного дерева во взвешенном графе в соответствии с запросом OP. Мою реализацию (на современном C++) можно найти здесь< /а>.

MST — это дерево, имеющее минимальный суммарный вес всех ребер графа. Таким образом, 2-й минимальный mst будет иметь 2-й минимальный суммарный вес всех ребер в графе.

пусть T -> BEST_MST (отсортируйте ребра в графе, затем найдите MST с помощью алгоритма Крускала)

T '-› 2-й лучший MST

допустим, у T есть 7 ребер, теперь, чтобы найти T ', мы будем одно за другим удалять одно из этих 7 ребер и найдем замену для этого ребра (стоимость этого ребра определенно будет больше, чем ребро, которое мы только что удалили из T ).

допустим исходный граф имеет 15 ребер

наш лучший MST ( T ) имеет 7 ребер

и 2-й лучший MST ( T ' ) также будет иметь только 7 ребер.

Как найти Т '

в T 7 ребер, теперь для всех этих 7 ребер удаляем их одно за другим и находим замену этим ребрам.

скажем, ребра в MST ( T ) --› { a,b,c,d,e,f,g }

скажем, наш ответ будет 2nd_BEST_MST, и изначально он имеет бесконечное значение (я знаю, что это звучит не очень хорошо, давайте пока просто предположим, что это так).

для всех ребер в BEST_MST:

current_edge = я нахожу замену для этого ребра, замена для этого ребра определенно будет иметь вес больше, чем i-е ребро (одно из 7 ребер) как мы собираемся найти замену для этого ребра, используя алгоритм Крускула (мы находим MST снова, поэтому мы будем использовать только алгоритм kruskal, но нам не нужно снова сортировать ребра, потому что мы сделали это, когда находили BEST_MST (T). вернуть 2nd_best_MST АЛГОРИТМ

скажем, исходный граф имеет 10 ребер, найдите BEST_MST (используя алгоритм kruskal) и предположим, что BEST_MST имеет только 6 ребер, но осталось 4 ребра, которых нет в BEST_MST (потому что их значение веса велико, и одно из этих ребер даст нам наш 2nd_Best_MST для каждого ребра «X», отсутствующего в BEST_MST (т.е. осталось 4 ребра), добавить это ребро в BEST_MST, которое создаст цикл, найти ребро «K» с максимальным весом в цикле (кроме new_added_edge «X» ) временно удалите ребро «K», которое сформирует новое связующее дерево, вычислите разницу в весе и сопоставьте weight_difference с ребром «X». Повторите шаг 4 для всех этих четырех ребер и верните связующее дерево с наименьшей разницей в весе в ЛУЧШИЙ_MST.