Крускалов алгоритам

Крускалов алгоритам је похлепни алгоритам који проналази минимално разапињућe стабло за повезани тежински граф. Ово значи да проналази подскуп грана које садрже све чворове, тако да је укупна тежина свих грана у стаблу минимална. Ако граф није повезан, онда проналази минималну разапињућу шуму (минимално разапињућe стабло за сваку компоненту повезаности).

Овај алгоритам се први пут јавља у Proceedings of the American Mathematical Society, Џозефа Крускала, 1956. године.

Други алгоритми за овај проблем укључују Примов алгоритам, Обрнуто-Брисање и Борувка алогритам.

Опис

• Направи шуму F (скуп стабала), где је сваки чвор у графу посебно стабло.
• Направи скуп S који садржи све гране у графу.
• Док је S непразно и F још увек није разапињућe:
  • уклони грану најмање тежине из S;
  • ако грана повезује два различата стабла, додај је у шуму, комбинујући два стабла у једно;
  • иначе, одбаци ту грану.

На крају алгоритма, шума формира минимално разапињућe стабло од графа. Ако је граф повезан, шума има једну компоненту и формира минимално разапињућe стабло.

Псеудокод

Наредни код је имплементиран коришћењем структуре раздвојених скупова:

KRUSKAL(G):
1 A = ∅
2 foreach v ∈ G.V:
3   MAKE-SET(v)
4 foreach (u, v) ordered by weight(u, v), increasing:
5    if FIND-SET(u) ≠ FIND-SET(v):
6       A = A ∪ {(u, v)}
7       UNION(u, v)
8 return A

Сложеност

Ако је E број грана у графу и V број чворова, за Крускалов алгоритам се може показати да се извршава у временској сложености O(E log E) или еквивалентној O(E log V), све за једноставне структуре података. Ова времена извршавања су еквивалентна зато што:

• E је највише V² и $\log V^{2}=2\log V$ $\;$ је O(log V).
• Сваки изоловани чвор је одвојена компонента минималне разапињућe шуме. Ако игноришемо изоловане чворове добијамо V ≤ E+1, па log V је O(log E).

Можемо да постигнемо ову границу на следећи начин: прво сортирамо чворове по тежини користећи сортирање поређењем (енг. comparison sort) и време O(Е log Е); ово допушта корак „уклони грану са минималном тежином из С“ да бисмо оперисали у константном времену. Следећe, користимо структуру раздвојених скупова да бисмо сачували евиденцију који чворови су у којим компонентама. Потребно је да извршимо O(Е) операција у O(E log V) времену. Довде је укупно време O(Е log Е) = O(E log V).

Ако обезбедимо да су гране или већ сортиране или да могу да буду сортиране за линеарно време (нпр. коришћењем counting sort-a или радикс сорта, алгоритам може да користи префињенију структуру раздвојених скупова, како би се извршавао у О(Е α(V)) времену, где је α екстремно споро растући инверз Акерманове функције са једном вредношћу.

Пример

Слика	Опис
	AD и CE су најкраћe гране, дужине 5 и AD је произвољно изабрана, па је означена.
	CE је сада најкраћа грана која не формира цикл, са дужином 5, па је означена као друга грана.
	Следећа грана, DF са дужином 6, означена је користећи исти метод.
	Наредне најкраћe гране су AB и BE, обе дужине 7. AB је произвољно изабрана и означена. Грана BD је означена црвеном бојом, јер већ постоји пут (зелене боје) између B и D, па би формирала цикл (ABD) да је изабрана.
	Процес се наставља за наредну најкраћу грану BE са дужином 7. Још доста грана је означено црвеном бојом у овом тренутку: BC јер би формирала петљу BCE, DE јер би формирала петљу DEBA и FE јер би формирала FEBAD.
	Најзад, процес се завршава са граном EG дужине 9 и пронађено је минимално разапињућe стабло.

Доказ коректности

Доказ се састоји из два дела. Прво, доказује се да алгоритам производи повезујућe стабло. Друго, доказује се да је конструисано повезујућe стабло минималне тежине.

Повезујућe стабло

Нека је $P$ повезан, тежински граф и нека је $Y$ подграф од $P$, добијен алгоритмом. $Y$ не може да има цикл, јер би последња додата грана била подстабло, а не између два различита стабла. $Y$ не може бити неповезан, јер би прва грана на коју наиђемо, а која спаја две компоненте из $Y$, била додата алгоритмом. Према томе, $Y$ је повезујућe стабло од $P$.

Минималност

Показујемо да је наредна претпоставка P тачна индукцијом: ако је F скуп грана изабраних у било ком стадијуму алгоритма, онда постоји минимално разапињућe стабло које садржи F.

• Очигледно, P је тачно на почетку, када је F празно: било које минимално разапињућe стабло ћe бити, а постоји једно, јер тежински повезани граф увек има минимално разапињућe стабло.
• Сада претпоставимо да је P тачно за неки бесконачан скуп F и нека је T минимално разапињућe стабло које садржи F. Ако је наредна изабрана грана e такође у T, онда је P тачно за F + e. Иначе, T + e има цикл C и постоји још једна грана f која је у C, а није у F. (Да нема такве гране f, e не би била додата у F, пошто би се тако креирао цикл C). Затим, T - f + e је стабло и има исту тежину као Т, пошто Т има минималну тежину и тежина од f не може бити мања од тежине e, иначе би алгоритам изабрао f уместо e. Тако је Т – f + e минимално разапињућe стабло које садржи F + e и још једном, P стоји.
• Због тога, по принципу индукције, P стоји када F постане разапињуће стабло, што је једино могуће ако је само F минимално разапињуће стабло.

Види још

• Алгоритам: Обрнуто-Брисање
• Дајкстрин алгоритам
• Примов алгоритам

Референце

• Joseph. B. Kruskal: On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. In: Proceedings of the American Mathematical Society, Vol 7, No. 1 (Feb, 1956)
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001.
• Michael T. Goodrich and Roberto Tamassia. Data Structures and Algorithms in Java, Fourth Edition. John Wiley & Sons, Inc., 2006.