Kruskal algoritmi

Kruskal algoritmi

Kruskal algoritmi

Kruskal algoritmi — grafning minimal qamrovchi daraxtini (MST) topishning mashhur usuli.
Bu ochko‘z algoritm bo‘lib, grafning barcha qirralari to‘plamidan qirralarni bittadan qo‘shib borib qamrovchi daraxtni quradi.

Asosiy g‘oya shundan iboratki:

• har bir cho‘qqi alohida daraxt hosil qilishidan boshlash;
• asta-sekin bu daraxtlarni minimal vaznli, sikl hosil qilmaydigan qirralarni qo‘shib birlashtirish.

Algoritm qadamlari

• Qirralarni saralash
  Grafning barcha qirralarini ularning vazni bo‘yicha o‘smas tartibda saralash.

• Initsializatsiya
  Har bir daraxt aynan bitta cho‘qqini o‘z ichiga oladigan $n$ ta daraxtdan iborat $F$ o‘rmonini yaratish.

• Qirralarni tanlash
  $F$ o‘rmoni bitta daraxtga aylanguncha quyidagi amallarni takrorlash:

  • sikl hosil qilmaydigan (uning uchlari turli daraxtlarga tegishli) eng kichik vaznli qirrani olish;
  • bu qirrani $F$ o‘rmoniga qo‘shib, ikki daraxtni birlashtirish.

• Natija
  Hosil bo‘lgan $$ o‘rmoni grafning minimal qamrovchi daraxti hisoblanadi.