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

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

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

Алгоритми Крускал — усули маъмули ёфтани дарахти остовии минималӣ (MST)-и граф.
Ин алгоритми ҳарисона аст, ки дарахти остовиро месозад, бо илова кардани қирраҳо якто-якто аз маҷмӯи ҳамаи қирраҳои граф.

Ғояи калидӣ дар он аст, ки:

• оғоз кардан аз он ки ҳар як қулла дарахти ҷудогона ташкил медиҳад;
• тадриҷан ин дарахтҳоро муттаҳид кардан, бо илова кардани қирраҳои вазни минималӣ, ки давраҳо ҳосил намекунанд.

Қадамҳои алгоритм

• Тартибдиҳии қирраҳо
  Ҳамаи қирраҳои графро бо тартиби ғайрикамшаванда аз рӯи вазнашон тартиб диҳед.

• Инициализатсия
  Ҷангал $F$-ро эҷод кунед, ки аз $n$ дарахт иборат аст, ки ҳар як дарахт маҳз як қулларо дар бар мегирад.

• Интихоби қирраҳо
  Амалҳои зеринро такрор кунед, то даме ки ҷангал $F$ ба як дарахт табдил наёбад:

  • қирраи аз рӯи вазн хурдтаринро гиред, ки давра эҷод намекунад (нӯгҳои он ба дарахтҳои гуногун тааллуқ доранд);
  • ин қирраро ба ҷангал $F$ илова кунед, ду дарахтро муттаҳид намуда.

• Натиҷа
  Ҷангали ҳосилшудаи дарахти остовии минималии граф мебошад.