изменение времени работы Prim - PullRequest
Новая
       27

изменение времени работы Prim

0 голосов
/ 25 февраля 2019

Я хотел найти «минимальное остовное дерево», учитывая набор A с ребрами, которые должны быть в «минимальном остовном дереве» (так что это не реальное минимальное остовное дерево, но учитывая A, оно имеет наименьшую суммувеса).Таким образом, «минимальное связующее дерево» должно обязательно содержать все ребра A. Я сделал некоторые модификации алгоритма Прима, которые можно найти ниже.Затем я хотел найти время выполнения этого алгоритма, однако у меня возникли проблемы с поиском времени выполнения, чтобы проверить, пусто ли пересечение двух множеств.Может ли кто-нибудь помочь мне?И каково будет общее время работы тогда?Я уже поместил время выполнения для каждого шага рядом с этим шагом, за исключением «?».

Уточнение обозначения: δ (W) = {{v, w} ∈ E: w ∈ W, v ∈ V\ W} для W ⊂ V 

algorithm:


1. T = ∅, W = {v}  for some v ∈ V   O(1)
2.  While W ≠ V                     n iterations
       If (A ∩ δ(W) ≠ ∅) do              ?
           Take e = {v,w}  ∈ (A ∩ δ(W))  O(1)
           T = T ∪ {e}                   O(1)
           W = W ∪ {v,w }                O(1)
       Else
           Find e = {v,w } ∈ δ(W) s.t. ce ≤ cf ∀ f ∈ δ(W)  O(m)  
           T = T ∪ {e}                                     O(1)
           W = W ∪ {v,w }                                  O(1)
   End while
...