Второе минное связующее дерево

Question

Я пишу алгоритм для поиска второго минимального связующего дерева. моя идея заключалась в следующем:

1. Используйте kruskals, чтобы найти самый низкий MST.
2. Удалить самый дешевый край MST.
3. Запустить kruskals снова на весь график.
4. вернуть новый MST.

Мой вопрос: будет ли это работать? Есть ли лучший способ, возможно, сделать это?

Answer 1

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

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

МСТ состоит из А-В-Д-С (6) стоимость. Вторая минимальная стоимость - A-B-C-D (стоимость 7). Если вы удалите край минимальной стоимости, вы получите вместо этого A-C-B-D (стоимость 105).

Так что ваша идея не будет работать. У меня нет лучшей идеи, хотя ...

Answer 2

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

1. Используйте Kruskals, чтобы найти MST.
2. Для каждого ребра в MST:
   1. Снять края от графа
   2. Вычислить MST»на MST
   3. Отслеживайте маленький MST
   4. Добавить край обратно к графу
3. Верните самый маленький MST.

Answer 3

Вы можете сделать это в O (V). Сначала вычислите MST с помощью Prim's algorithm (может быть сделано в 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.

Here's a link в псевдокод и более подробные пояснения.

Answer 4

Ниже приведен алгоритм, который вычислить 2-го минимального остовного дерева в O (N^2)

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

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

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

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

4. Вычислить массу вновь образованного дерева. Допустим, W=weight(T)-weight(e)+weight(e')

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

Answer 5

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

После обнаружения MST,

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

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

Решение из следующей связи.
http://web.mit.edu/6.263/www/quiz1-f05-sol.pdf

Answer 6

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

Answer 7

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

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