Back

ⓘ Алгоритам обрнутог брисања




                                     

ⓘ Алгоритам обрнутог брисања

Алгоритам обрнутог брисања је алгоритам у теорији графова који се користи за добијање минималног разапињућег стабла из датог повезаног тежинскоg графа. Он се први пут појавио kод Kрускалa 1956, али то не треба мешати са алгоритмом Крускала који се помиње у овој области. Уколико граф није повезан, овај алгоритам ће наћи минимално разапињуће стабло, одвојено за сваки део графа. Скуп ових минималних разапињућих стабала се зове минимална разапињућа шума, која садржи сваки чвор графа.

Овај алгоритам је похлепни алгоритам, бира најбољи избор у сваком тренутку у задатој ситуацији. То је супротно од Крускаловог алгоритма, што је још један похлепни алгоритам који проналази минимално Разапињуће стабло. Крускалов алгоритам почиње са празним графом и додаје гране, док обрнуто брисање почиње са оригиналном графом и брише из њега гране. Алгоритам ради на следећи начин:

  • За сваку грану, проверите да ли ће брисање направити неповезан граф.
  • Извршите брисања која не доводе до додатних искључења.
  • Почиње са графом Г, који садржи листу грана Е.
  • Иде до Е по опадајућем редоследу тежине грана.
                                     

1. Псеудокод

1 function ReverseDelete(edges E

Горњи граф је скуп грана Е где свака грана има тежину и повезује чворове v1 и v2.

                                     

2. Време извршавања

За алгоритам се може доказати да ради у О E log V log V 3) времену, где је је број грама и V је број чворова. Ова граница се достиже на следећи начин:

  • Брисање у О 1 времену
  • Е итерације петље
  • Сортирање грана по тежини помоћу поређења у О Е лог Е времену
  • Повезивање проверити у O log V log V 3) времену Thorup 2000.

Исто тако, време рада може се сматрати О E log E log E 3) јер највећи Е може се V 2. Запамтите да log V 2 = 2 * log V, па 2 је мултипликативна константа која ће бити игнорисана у нотацији великог O.