Второе лучшее минимальное остовное дерево

Предпосылки — Граф, Остовное дерево, Непересекающееся множество (Объединение — Найти).

A minimum spanning tree (MST) T, for a given graph G, spans over all vertices of a given graph and has minimum weight sum of all edges, out of all the possible spanning trees. 

Second best MST, T’, is a spanning tree with the second minimum weight sum of all edges, out of all spanning trees of graph G.

T и T' отличаются только одной заменой ребер. Таким образом, мы должны найти ребро e _new , которого нет в T, и заменить его ребром в T (скажем, e _old ), таким образом, что T' = T union {e _new } – {e _old } является остовным деревом, а разность весов of (e _new – e _old ) минимально (e _new , e _old – ребра в графе G).

Используя алгоритм Крускала -

• Используйте алгоритм Крускала, чтобы найти MST T графа G. Удалите из него одно ребро и замените его другим, чтобы получить T'.
• Отсортируйте ребра за время O (ElogE) (E-количество ребер) и найдите MST, используя алгоритм Крускала, за время O (E) (количество ребер в MST = V-1, где V = количество вершин в графе ГРАММ).
• Для каждого ребра в MST временно исключим его из списка ребер (чтобы мы не могли его выбрать).
• Затем попытайтесь найти MST в O(E), используя оставшиеся ребра. (не нужно снова сортировать)
• Повторите вышеописанное для всех ребер в MST и выберите лучшее. (со 2-й минимальной суммой веса). Таким образом, мы получили T' – второй лучший MST.
• Общая временная сложность — O (ElogE + E + VE) = O (VE)

Ниже приведена реализация вышеуказанного подхода:

Временная сложность — O(VE), где V — количество вершин во входном графе, E — количество ребер во входном графе.