Алгоритам обрнутог брисања је алгоритам у теорији графова који се користи за добијање минималног разапињућег стабла из датог повезаног тежинскоg графа .
Он се први пут појавио kод Kрускалa 1956, али то не треба мешати са алгоритмом Крускала који се помиње у овој области. Уколико граф није повезан, овај алгоритам ће наћи минимално разапињуће стабло, одвојено за сваки део графа. Скуп ових минималних разапињућих стабала се зове минимална разапињућа шума, која садржи сваки чвор графа.
Овај алгоритам је похлепни алгоритам, бира најбољи избор у сваком тренутку у задатој ситуацији. То је супротно од Крускаловог алгоритма, што је још један похлепни алгоритам који проналази минимално Разапињуће стабло. Крускалов алгоритам почиње са празним графом и додаје гране, док обрнуто брисање почиње са оригиналном графом и брише из њега гране. Алгоритам ради на следећи начин:
1 function ReverseDelete(edges[] E) 2 sort E in decreasing order 3 Define an index i ← 0 4 while i < size(E) 5 Define edge temp ← E[i] 6 delete E[i] 7 if temp.v1 is not connected to temp.v2 8 E[i] ← temp 9 i ← i + 1 10 return edges[] E
Горњи граф је скуп грана Е где свака грана има тежину и повезује чворове v1 и v2.
У следећем примеру зелене гране се процењују у алгоритму а црвене гране су избрисане.
За алгоритам се може доказати да ради у О (E log V (log log V)3) времену, где јеЕ је број грама и V је број чворова. Ова граница се достиже на следећи начин:
Исто тако, време рада може се сматрати О (E log E (log log E)3) јер највећи Е може се V 2. Запамтите да logV 2 = 2 * log V, па 2 је мултипликативна константа која ће бити игнорисана у нотацији великог O.
This article uses material from the Wikipedia Српски / Srpski article Алгоритам обрнутог брисања, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Садржај је доступан под лиценцом CC BY-SA 4.0 осим ако је другачије наведено. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Српски / Srpski (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.