logo

KRASKAL ALGORITMI

Загружено в:

12.08.2023

Скачано:

0

Размер:

439.9208984375 KB
“KRASKAL ALGORITMI” MAVZUSIDA TAYYORLAGAN
 
Mundarija
 Kirish. ............................................................................................................................................................................. 2
Kraskal algoritmi. ............................................................................................................................................................ 3
Kraskal algoritmining tavsifi. ......................................................................................................................................... 7
Algoritmning psevdokodi. ............................................................................................................................................ 16
Kraskalning minimal kengayuvchi daraxt algoritmi. .................................................................................................... 20
Algoritmning amaliy qismi. .......................................................................................................................................... 28
Kraskal algoritmining murakkabligi. ............................................................................................................................ 35
Xulosa. .......................................................................................................................................................................... 40
Foydanilgan adabiyotlar. ............................................................................................................................................... 41
1 Kirish.
Kurs   ishining   o’rganish   ob’ekti   Kraskal   algoritmini   amalga   oshirish   edi.
Ishning maqsadlari quyidagilar edi: 
1)kraskal algoritmi, uning tarixi bilan tanishish;
2)minimal kenglikdagi daraxtni qurish algoritmini amalga oshirish;
3)algoritmning murakkabligini tahlil qilish;
4)algoritmni sinash.
Bog’langan vaznli grafning minimal oraliq daraxti (MOD) uning bog’langan
pastki   grafigi   bo’lib,   u   asl   daraxtning   barcha   uchlari   va   uning   ba’zi   qirralaridan
iborat   bo’lib,   qirralarning   og’irliklarining   yig’indisi   maksimal   mumkin.   Agar   asl
graf   uzilgan   bo’lsa,   unda   quyida   tavsiflangan   protsedura   uning   har   bir   ulangan
komponentiga navbat bilan qo’llanilishi mumkin va shu bilan ushbu komponentlar
uchun   minimal   oraliq   daraxtlarni   olish   mumkin.   Kraskal   algoritmi   (yoki   Kraskal
algoritmi) vaznli bog langan yo naltirilmagan graf uchun minimal oraliqli daraxtniʻ ʻ
qurish   algoritmidir.   Algoritm   birinchi   marta   1956   yilda   Jozef   Kraskal   tomonidan
tasvirlangan.   Kraskal   algoritmi   bir   vaqtning   o’zida   bir   nechta   bog’langan
komponentlar   uchun   daraxt   qurishi   mumkin,   ular   hal   qilish   jarayonida   bitta
bog’langan daraxtga birlashtiriladi.  To’liq graf qirralarning ro’yxati bilan berilgan.
Yugurishdan   oldin   qirralarning   ro’yxati   uzunlik   bo’yicha   o’sish   tartibida
tartiblanadi.   Har   bir   bosqichda   qirralarning   ro’yxati   ko’rib   chiqiladi,   oldingi
bosqichdagi   yechimga   kiritilganidan   keyingi   qirraidan   boshlab,   eritma   ichiga
kiritilgan   qirralar   bilan   sikl   hosil   qilmaydigan   qirra   pastki   daraxtga   qo’shiladi.
qurilish ishlari olib borilmoqda. Daraxtning minimal uzunligini topish muammosi
ko’pincha shunga o’xshash sharoitda yuzaga keladi: n ta shahar bor, ular orqali siz
istalgan   shahardan   boshqasiga   (to’g’ridan-to’g’ri   yoki   boshqa   shaharlar   orqali)
borishingiz   mumkin   bo’lgan   marshrutni   yotqizishingiz   mumkin.   Yo’l   haqi
maksimal bo’lishi uchun shunday marshrutni topish talab qilinadi. Amalda Kraskal
2 algoritmi   aviakompaniyalar   tomonidan   bir   yo’nalishdan   ikkinchisiga   eng   qisqa
havo yo’lini topishda qo’llaniladi. 
Kraskal algoritmi.
Kraskal   algoritmi   bog’langan   vaznli   graf   uchun   minimal   oraliq   daraxtini
topish uchun ishlatiladi.   Algoritmning asosiy maqsadi biz grafning har bir tugunini
kesib o’tishimiz mumkin bo’lgan qirralarning pastki to’plamini topishdir.   U global
optimalga   e’tibor   qaratish   o’rniga   har   bir   bosqichda   optimal   echim   topadigan
greedy yondashuvga amal qiladi.
Kraskal   algoritmi   bu   grafning   MODni   topish   uchun   boshqa   mantiqdan
foydalanadigan   yana   bir   mashhur   minimal   oraliqli   daraxt   algoritmi.   Kraskal
algoritmi   tugundan   boshlash   o’rniga,   barcha   qirralarni   past   og’irlikdan   yuqoriga
saralaydi   va   siklni   yaratadigan   qirralarga   e’tibor   bermasdan,   eng   past   qirralarni
qo’shishda davom etadi.
Kraskal algoritmi dastlab har bir tugunni o’z daraxtiga joylashtiradi, so’ngra
bu   daraxtlarni   asta-sekin   birlashtirib,   har   bir   iteratsiyada   qaysidir   qirrada   ikkita
ma’lum   daraxtni   birlashtiradi.   Algoritmni   boshlashdan   oldin   barcha   qirralarning
vazni   bo’yicha   (kamaymaslik   tartibida)   tartiblanadi.   Keyin   birlashtirish   jarayoni
boshlanadi: barcha qirralar birinchisidan oxirgisiga (tartib tartibida) o’tkaziladi va
agar joriy qirraning uchlari turli pastki daraxtlarga tegishli bo’lsa, u holda bu pastki
daraxtlar  birlashtiriladi   va  javobga  qirra  qo’shiladi.   Barcha  qirralarni  sanab   o’tish
oxirida barcha tugunliklar bir xil pastki daraxtga tegishli bo’ladi va javob topiladi.
Bizda   quyidagi   yo’naltirilmagan   vaznli   graf   mavjud,   grafning   barcha   tugunlarini
o’z ichiga olgan pastki graf, ya’ni daraxt bo’lgan kengaytmali daraxt deb ataymiz
va   vazifa   -   qirralarining   yig’indisi   minimal   bo’lgan   bunday   kengaygan   daraxtni
topishdir.
Asl   grafni   qirralarsiz   tasavvur   qiling,   endi   siz   barcha   tugunlarni   qandaydir
tarzda   bir-biriga   bog’lashingiz   kerak,   shunda   siz   istalgan   tugundan   ikkinchisiga
3 o’tishingiz mumkin, natijada olingan grafda kiritilgan qirralarning og’irliklarining
minimal mumkin bo’lgan yig’indisi bilan sikllarsiz ishlaydi.
Ushbu   algoritmning   ishlash   mexanizmi   juda  oddiy.   Kirish   qismida   bo’sh   subgraf
mavjud bo’lib, biz uni potentsial minimal kenglikdagi daraxtga yakunlaymiz.
Biz   faqat   bog’langan   graflarni   ko’rib   chiqamiz,   aks   holda   Kraskal   algoritmini
qo’llashda   biz   minimal   kenglikdagi   daraxtni   emas,   balki   oddiygina   o’rmonni
olamiz.
 Birinchidan,   biz   qirralarni   og’irliklari   bo’yicha   kamaymaydigan   tartibda
saralaymiz.
 Biz   subgrafimizga   qirra   qo’shamiz i- ое ,   agar   bu   qirra   ikki   xil   bog’langan
komponentni   bog’lasa,   ulardan   biri   bizning   subgrafimizdir.   Ya’ni,   har   bir
qadamda   minimal   og’irlik   qirrasi   qo’shiladi,   uning   bir   uchi   bizning
subgrafimizda mavjud, ikkinchisi esa hali yo’q.
 Algoritm o’z ishini subgrafimizning tugunlari to’plami asl grafning tugunlari
to’plamiga to’g’ri kelgandan keyin yakunlaydi.
Ushbu   algoritm   greedy   deb   ataladi,   chunki   har   bir   qadamda   biz   umuman
optimal yechimga olib keladigan eng yaxshi variantni topishga harakat qilamiz.
Muayyan misolni bosqichma-bosqich tahlil qilish.
Quyda   keltirilgan   grafdan   biz   uning   barcha   qirralarini   tartiblangan   tartibda
yozamiz, va biz ushbu qirralarni ro’yxatdagi  skeletimizga qo’shishni  boshlaymiz:
1)   D   <-->   B;   w   =   2
2)   D   <-->   C;   w   =   6
4 3)   A   <-->   B;   w   =   7
4)   A   <-->   C;   w   =   8
5)   C   <-->   E;   w   =   9
6)   D   <-->   F;   w   =   9
7)   F   <-->   E;   w   =   10
8)   B   <-->   C;   w   =   11
9) D <--> E; w = 11
1-qirra   qo’shgandan   keyin   pastki   chiziq
2 va 3 qirralarni qo’shgandan so’ng subgraph  A <--> C 
Ko’rib   turganingizdek,   bizning   kengaygan   daraxtimizga   qirra   qo’shsangiz,   sikl
hosil bo’ladi, shuning uchun biz bu qirrani o’tkazib yuboramiz.
Natijada, bizda quyidagi subgraf bor va siz sezganingizdek, biz barcha tugunlarni
qirralar bilan minimal mumkin bo’lgan og’irliklar bilan birlashtirdik, ya’ni biz asl
grafmiz uchun minimal oraliq daraxtini topdik.
5 MOD   ni   graphonline   -da   topish   uchun   biz   o’rnatilgan   algoritm   bilan   tekshiramiz
va   biz   pastki   graflar   bir   xil   ekanligini   ko’ramiz     agar   qirralarning   og’irligi   teng
bo’lsa,   biz   ulardan   istalganini   tanlashimiz   mumkinligi   sababli,   eng   kam
kenglikdagi   daraxtlar   bo’lgan   oxirgi   subgraflar   ba’zi   qirralarga   qadar   farq   qilishi
mumkin.
Istalgan MODning umumiy og’irligi 33 ni tashkil qiladi.
Amalga oshirish .   Taqdim etilgan algoritmni amalga oshirishning eng oson yo’li –
KST   (kesishmayotgan   segmentlar   tizimi)   yordamida.   Avval   aytib   o’tganimizdek,
qirralarning   og’irligiga   qarab   kamaymaydigan   tartibda   saralash   kerak.   Bundan
tashqari,   funktsiya   chaqiruvlari   yordamida   biz   har   bir   tugunni   o’z   daraxtimizga
joylashtirishimiz   mumkin,   ya’ni   biz   ma’lum   bir   pastki   graf   to’plamini   yaratamiz.
Keyin   biz   barcha   qirralarni   tartiblangan   tartibda   takrorlaymiz   va   joriy   qirraning
tushayotgan  uchlari  funktsiyadan  foydalangan  holda   turli   pastki  graflarga   tegishli
yoki   yo’qligini   ko’ramiz,   agar   ikkala   uchi   ham   turli   komponentlarda   bo’lsa,   u
holda funksiya yordamida ikkita turli pastki grafni birlashtiramiz. 
6 Kraskal algoritmining tavsifi.
Algoritm   V   turli   guruhlardan   boshlanadi   (bu   erda   V   -   grafdagi   tugunlar
soni).   Jarayonning   har   bir   bosqichida   grafning   minimal   og’irligi   bo’lgan   qirra
tanlanadi   va   minimal   oraliq   daraxtga   qo’shiladi.   Qirra   faqat   shunday   tarzda
tanlanadi,   agar   u   sikl   yaratmasa   -   agar   minimal   og’irlikdagi   qirra   minimal   oraliq
daraxtda siklni keltirib chiqarsa, algoritm ikkinchi minimal og’irlikdagi qirra bilan
davom   etadi.   Grafga   qirra   qo’shish,   shuningdek,   ikkala   tugunni   ham   bir   guruhga
aylantiradi   (esda   tutingki,   har   bir   tugun   dastlab   alohida   guruhlarda
boshlanadi).   Algoritm tugagandan so’ng, faqat bitta guruh qoladi, bu esa minimal
kenglikdagi daraxtni ifodalaydi.
C++   Kraskal   algoritmi   Prim   algoritmidan   bir   oz   boshqacha   ishlaydi.   Prim
algoritmi   tugunlarni   ushbu   guruhga   suradi   va   uni   minimal   og’irlikdagi   qirrani
tashkil   etuvchi   ikkita   tugundan   boshlab   birma-bir   kengaytiradi.   Kraskal   algoritmi
tugunlarga   emas,   balki   qirralarga   ko’proq   taalluqlidir   va   ularning   uchlarini
umumiy guruhga qo’shish orqali to’g’ridan-to’g’ri qirralar bilan shug’ullanadi.
C++   da   Kraskal   algoritmini   amalga   oshirishning   ikkita   asosiy   usuli   mavjud:
ajratilgan  to’plamlar   yoki  ustuvor   navbatlar.   Ajratilgan  to’plamlardan  foydalanish
biroz   yaxshiroq,   chunki   u   istalgan   vaqtda   guruhlardagi   o’zgarishlarni   tasavvur
qilishga yordam beradi.
Algoritm quyidagicha: -
1. Tugunlar guruhlarini saqlash uchun massivni ishga tushiring.
2. Graf   qirralarini   ularning   og’irliklari   bilan   saqlash   uchun   massivni   ishga
tushiring.
3. Yopuvchi daraxtni bo’sh massiv sifatida ishga tushiring.
7 4. Grafning barcha uchlarini turli guruhlarga qo’ying.
5. Qirralar qatorini og’irliklarning ortib borishi bo’yicha tartiblang.
6. Kenarlarning   tartiblangan   qatorida   boshqa   qirra   qolmaguncha   7-bosqichni
davom ettiring
7. Agar qirraning bir tugunining guruhi qirraning boshqa tugunining guruhiga
to’g’ri   kelmasa,   ularni   ikkalasini   ham   bir   guruhga   qo’shing   va   qirrani
kengaytirilgan daraxt qatoriga qo’shing.
8. Spaning-tree   massivi   bo’ylab   takrorlang   va   qirralarning   og’irliklarini
qo’shing.
9. Olingan   qirralarning   yig’indisi   eng   kam   yoyiladigan   daraxtning   og’irligini
tashkil   qiladi,   shu   bilan   birga   kengayuvchi   daraxtlar   qatori   ham   xuddi
shunday qirralarni o’z ichiga oladi.
Keling,   bir   misol   ishlab   chiqaylik.   Yuqoridagi   grafni   ko’rib   chiqing   va   unga
Kraskal algoritmini qo’llashga harakat qilaylik.
8 Dastlab,   biz   minimal   vaznga   ega   bo’lgan   birinchi   qirrani   tanlashimiz   kerak.   Bu
erda AB tanlanadi, uning og’irligi 10 ga teng.
9 Endi biz ikkinchi minimal og’irlik bilan qirrasini tanlaymiz.   Bu erda disk og’irligi
13 bo’lgani uchun tanlanadi.
10 Keyinchalik   davom   etsak,   minimal   og’irlikdagi   qirra   BC   ekanligini
aniqlaymiz.   Ushbu qirraning og’irligi 18 ga teng.
11 To’liq   daraxt   olinganligi   sababli,   biz   algoritmni   bu   erda   to’xtatamiz.   Shu   tarzda
olingan daraxtning minimal og’irligi 10+18+13=41.
Dastlab, joriy qirralar to’plami bo’sh qilib o’rnatiladi. Keyin, iloji bo’lsa, quyidagi
operatsiya   amalga   oshiriladi:   mavjud   to’plamga   qo’shilishi   unda   sikl   paydo
bo’lishiga   olib   kelmaydigan   barcha   qirralardan   minimal   og’irlikning   qirrasi
tanlanadi   va   allaqachon   mavjud   to’plamga   qo’shiladi.   Bunday   qirralar
qolmaganda,  algoritm   tugallanadi.   Berilgan  grafning  barcha  tugunlari   va  topilgan
qirralari   to’plamini   o’z   ichiga   olgan   pastki   grafigi   uning   minimal   og’irlikdagi
daraxtidir.   Algoritm   quyidagi   harakatlar   ketma-ketligidan   iborat:     E   qirralari
ro yxati tuziladi, unda qirraning uzunligi, qirraning boshlang ich cho qqisi soni (i),ʻ ʻ ʻ
12 qirraning oxirgi uchi soni (j) va bu qirraga kiritilganligi belgisi ko rsatilgan daraxt.ʻ
2.   Ushbu   ro’yxat   qirra   uzunligi   bo’yicha   o’sish   tartibida   tartiblangan.   E   ro’yxati
ko’rib   chiqiladi   va   undan   maksimal   uzunlikdagi   qirra   tanlanadi,   u   hali   hosil
bo’lgan   daraxtga   kiritilmagan   va   allaqachon   qurilgan   qirralari   bilan   siklni   tashkil
qilmaydi. Agar barcha uchlari daraxtga kiritilgan bo’lsa va qirralarning soni uchlari
sonidan bitta kam bo’lsa, algoritm o’z ishini tugatdi. Aks holda, 3-bandga qayting. 
Kraskal algoritmini tushunish uchun quyidagi misolni ko’rib chiqamiz -
1-qadam - Barcha halqalarni va parallel qirralarni olib tashlang
Berilgan grafdan barcha halqalarni va parallel qirralarni olib tashlang.
Parallel qirralar bo’lsa, eng kam xarajatga ega bo’lganini saqlang va qolganlarini
olib tashlang.
13 2-qadam - Barcha qirralarning og’irlik ortib borayotgan tartibida joylashtiring
Keyingi qadam, qirralar va og’irliklar to’plamini yaratish va ularni og’irlik (narx)
bo’yicha o’sish tartibida joylashtirishdir.
3- qadam  -  Eng   kam   vaznga   ega   bo ’ lgan   qirrani   qo ’ shing
Endi   biz   eng   kichik   vaznga   ega   bo ’ lganidan   boshlab   grafga   qirralarni   qo ’ shishni
boshlaymiz .   Butun   vaqt   davomida   biz   oraliq   xususiyatlarining   buzilmaganligini
tekshirishda davom etamiz.   Agar bitta qirra qo’shilganda, oraliq daraxt xususiyati
mos kelmasa, biz qirrani grafga kiritmaslikni ko’rib chiqamiz.
Eng   kam   xarajat   2   va   B,   D   va   D,   T   bilan   bog’liq   qirralar.   Biz   ularni
qo’shamiz.   Ularni   qo’shish   keng   tarqalgan   daraxt   xususiyatlarini   buzmaydi,
shuning uchun biz keyingi qirra tanlovimizni davom ettiramiz.
Keyingi   xarajat   -   3   va   bog’langan   qirralar   A,   C   va   C,   D.   Biz   ularni   yana
qo’shamiz -
14 Jadvaldagi   keyingi   xarajat   4   ga   teng   va   biz   uni   qo’shish   grafda   sxema   hosil
qilishini kuzatamiz.  
Biz  buni  e’tiborsiz  qoldiramiz.   Bu  jarayonda  biz  kontaktlarning  zanglashiga  olib
keladigan barcha qirralarni e’tiborsiz qoldiramiz qirralab o’tamiz.
5   va   6   qiymatiga   ega   bo’lgan   qirralarning   ham   sxemalar   hosil   qilishini
kuzatamiz.   Biz ularga e’tibor bermaymiz va davom etamiz.
15 Endi  bizda faqat  bitta tugun qo’shilishi  kerak.   Mavjud bo’lgan 7 va 8 ikkita eng
kam xarajat qirralari o’rtasida biz 7 narxiga ega qirrani qo’shamiz.
S, A qirralarini qo’shish orqali biz grafning barcha tugunlarini o’z ichiga oldik va
endi biz minimal xarajatlarni qamrab oluvchi daraxtga egamiz. Shu   bilan   Kraskal
algoritmi   o ’ z   ishini   yakunlaydi .
Algoritmning psevdokodi.
Kraskal   psevdokodi   juda   oson   tushunarsiz   kod   deb   atash   mumkin.   Axir,   agar   bu
juda   aniq   bo’lsa,   nima   uchun   barcha   sharhlar   satrlari?   Mening   fikrimcha,   sof
Python-dan   foydalanish   foydaliroq   matn   bo’ladi   (sof   aytganda,   uchinchi   tomon
kutubxonalari   kerak   emas).   Misol   uchun,   quyidagi   ommaviy   domen   qidiruvi
(Guido tomonidan) hech qanday izohga ega emas va ko’pchilik o’quvchilar uchun
tushunarli bo’lishi kerak.
def find_path (graph, start, end, path = []):
  path = path + [start]
  if start == end:
    return path
  if not graph.has_key(start):
    return None
  for node in graph[start]:
    if node not in path:
16       newpath = find_path (graph, node, end, path)
      if newpath: return newpath
  return None
Agar   men   klasterdan   fo ydalanishni   va   har   bir   tugun   uchun   klasterlarni
birlashtirgandan   keyin   qaysi   tugunga   tayinlanishi   kerakligini   aniqlay   olsam,   uni
Pythonga qo’yishga harakat qilgan bo’lardim.
Shu   bilan   bir   qatorda,   bu   yuqoridagi   qidiruvdan   foydalangan   holda   mening
taklifim bo’ladi.
def Kraskal(graph):
  tree = {}
  nodes=node_list(graph)
  n=len(nodes)
  edges = graph. Keys ()
  edges. Sort (key=lambda x:graph[x][2])
  for e in edges:
    v=graph[e]
    loop=find_path (tree, v[1], v[0])
    if not loop:
      tree[e]=v
      if len(tree)>n-2: break
  return tree
Quyidagi kod ajratilgan ma’lumotlar tuzilmasi bilan amalga oshiriladi. Bu erda biz
F   o’rmonimizni   qirralar   to’plami   sifatida   ko’rsatamiz   va   ikkita   tugun   bir
17 daraxtning   bir   qismi   ekanligini   samarali   aniqlash   uchun   ajratilgan   ma’lumotlar
strukturasidan foydalanamiz.   
algorithm  Kraskal( G )  is
    F:=  ∅
     for each  v  ∈  G.V  do
        MAKE-SET(v)
     for each  (u, v)  in  G.E ordered by weight (u, v), increasing  do
         if  FIND-SET(u) ≠ FIND-SET(v)  then
            F:= F  ∪  {(u, v)}  ∪  {(v, u)}
            UNION(FIND-SET(u), FIND-SET(v))
     return  F
Har   qanday   minimal   kengaytm ali   daraxt   algoritmi   qirra   qo’shish   halqa   hosil
qiladimi yoki yo’qligini tekshirish atrofida aylanadi.
Buni   aniqlashning   eng   keng   tarqalgan   usuli   Union   FInd   deb   nomlangan
algoritmdir.   Union-Find   algoritmi   tugunlarni   klasterlarga   ajratadi   va   bizga   ikkita
tugun   bir   xil   klasterga   tegishli   yoki   yo’qligini   tekshirishga   imkon   beradi   va
shuning uchun qirra qo’shish sikl hosil qiladimi yoki yo’qligini hal qiladi.
KRASKAL(G):
A =  ∅
For each vertex v  ∈  G.V:
    MAKE- SET (v)
For   each  edge (u, v)  ∈  G.E ordered  by  increasing  order   by  weight(u, v):
     if  FIND- SET (u) ≠ FIND- SET (v):       
    A = A  ∪  {(u, v)}
     UNION (u, v)
return  A
                                                                                                                                   
Algoritmning   psevdokodi   Qirralarni   og’irliklarning   o’sish   tartibida   tartiblang
18 ajratilgan   strukturani   ishga   tushiring   edgeCount=l   esa   edgeCount<=E   va
includeCount<=M-l   do   parentl=FindRoot   (qirra   [edgeCount].   start)   =   FindRoot
(qirra   [edgeCount].   end)parentl/=parent2   keyin   qirra   [edgeCount]   ni   kengaytmali
daraxtga qo’shing = includedCount = l (parent1,parent2) if = edgeCount + l while -
grafdagi   qirralarning   soni;   V   -   grafdagi   uchlari   soni   edgeCount   -   o’zgaruvchi;
includeCount   -   o’zgaruvchi;   -   biz   ishlamoqchi   bo’lgan   to’plamning   har   bir
elementi uchun bitta katak ajratilgan massiv; FindRoot (x) - (x - biz uni o’z ichiga
olgan   qismning   ildizini   topmoqchi   bo’lgan   element)   x   elementining   bevosita
ajdodining raqamini saqlaydigan Ota [x] katakchasidan boshlanadigan protsedura;
- a ikki qismning birlashmasini bajaradigan funksiya.
19 Kraskalning minimal kengayuvchi daraxt algoritmi.
Kraskal  algoritmidan foydalanishning  asosiy  maqsadi  graf  uchun minimal  xarajat
daraxtini   olishdir.   Biroq,   agar   siz   minimal   kenglikdagi   daraxt   nima   ekanligini
tushunmasangiz, bu mantiqiy emas.   Bu misol bilan eng yaxshi tushuntirish bo’lishi
mumkin. Aytaylik, bizda shunday graf bor:
Bizda   to’rtta   tugun   bor,   A,   B,   C   va   D.   Biz   sikllarni   olib   tashlash   va   daraxt   hosil
qilish  uchun grafning  turli   qirralarini  o’zgartirishimiz  mumkin.   Bu  bir   necha  usul
bilan amalga oshirilishi mumkin: 
20 Bu holda daraxtning vazni 22+21+13=56 ga teng.
21 Bu holda daraxtning vazni 10+22+21=53 ga teng.
Bu holda daraxtning vazni 10+18+13=41 ga teng.   Ehtiyotkorlik bilan solishtirsak,
bu   daraxt   barcha   olingan   daraxtlar   orasida   minimal   vaznga   ega   ekanligini
ko’rishimiz   mumkin.     Kraskal   algoritmining   asosiy   maqsadi   ushbu   minimal
kenglikdagi   daraxtni   olishdir.   Qirralarning   og’irliklarining   yig’indisi   minimal
bo’lgan grafdan olingan daraxt minimal kengayuvchi daraxt deyiladi.
Minimal   kengayuvchi   daraxt   bu   bog’langan   va   yo’naltirilmagan   graf
berilgan   bo’lsa,   ushbu   grafning   kengayuvchi   daraxti   daraxt   bo’lgan   va   barcha
tugunlarni   bir-biriga   bog’laydigan   pastki   grafdir.   Bitta   grafda   juda   ko’p   turli   xil
daraxtlar   bo’lishi   mumkin.   Og’irlangan ,   bog’langan,   yo’naltirilmagan   graf   uchun
minimal   oraliq   daraxti   (MOD)   yoki   minimal   og’irlik   oralig’i   daraxti   og’irligi   har
bir   boshqa   kengayuvchi   daraxtning   og’irligidan   kam   yoki   teng   bo’lgan
kengayuvchi   daraxtdir.   Yostiqli   daraxtning   og’irligi   -   bu   daraxtning       yig’indisi.
Minimal   kenglikdagi   daraxtning   nechta   qirrasi   bor?     Minimal   kenglikdagi
daraxtning (V - 1) qirralari bor, bu erda V - berilgan grafdagi tugunlar soni.
22 Quyida Kraskal algoritmi yordamida MOD ni topish bosqichlari keltirilgan
1.   Barcha   qirralarni   og’irligining   kamaymaydigan   tartibida   tartiblang.  
2.   Eng   kichik   qirraini   tanlang.   Hozirgacha   hosil   bo’lgan   oraliq   daraxt   bilan   sikl
hosil   qilishini   tekshiring.   Agar   sikl   hosil   bo’lmasa,   bu   qirra   qo’shing.   Aks   holda,
uni   tashlang.  
3.   2-bosqichni o’tish daraxtida (V-1) qirralar paydo bo’lguncha takrorlang.
2-qadam   sikllarni   aniqlash   uchun   Union-Find   algoritmidan   foydalanadi.   Shuning
uchun   biz   old   shart   sifatida   quyidagi   postni   o’qishni   tavsiya   qilamiz.  
Birlashma-topish   algoritmi   1-to’plam   (Grafdagi   siklni   aniqlash)    
Birlashma-topish   algoritmi   2-to’plam   (Rank   va   yo’l   bo’yicha   siqilish)
Algoritm greedy algoritmdir.   Greedylik tanlovi hozirgacha  qurilgan MODda siklga
olib   kelmaydigan   eng   kichik   og’irlik   chegarasini   tanlashdir.   Keling,   buni   misol
bilan   tushunamiz:   Quyidagi   kirish   grafigini   ko’rib   chiqing.  
 
Grafda 9 ta tugun va 14 ta burchak mavjud.   Shunday qilib, hosil bo’lgan minimal
kenglikdagi daraxt (9 - 1) = 8 qirraga ega bo’ladi.  
Saralashdan keyin: 
Og’irligi Src Dest 
1 7 6 
2 8 2 
23 2 6 5 
4 0 1 
4 2 5 
6 8 6 
7 2 3 
7 7 8 
8 0 7 
8 1 2 
9 3 4 
10 5 4 
11 1 7 
14 35
Endi   qirralarning   saralangan   ro’yxatidan   barcha   qirralarni   birma-bir   tanlang
1.   7-6   qirraini   tanlang:   Hech   qanday   sikl   hosil   bo’lmaydi,   uni   qo’shing.  
 
2.   Pick   qirrasi   8-2:   Hech   qanday   sikl   hosil   bo’lmaydi,   uni   qo’shing.  
 
24 3.   Pick   qirrasi   6-5:   Hech   qanday   sikl   hosil   bo’lmaydi,   uni   qo’shing.  
 
4.   Pick   qirrasi   0-1:   Hech   qanday   sikl   hosil   bo’lmaydi,   uni   qo’shing.  
 
5.   Pick   qirrasi   2-5:   Hech   qanday   sikl   hosil   bo’lmaydi,   uni   qo’shing.  
 
6.   8-6-chi qirralarni tanlang:   Ushbu qirra qo’shilishi siklga olib kelganligi sababli,
uni tashlang.
25 7.   Pick   qirrasi   2-3:   Hech   qanday   sikl   hosil   bo’lmaydi,   uni   qo’shing.  
 
8.   7-8   qirrani   tanlang:   Ushbu   qirra   qo’shilishi   siklga   olib   kelganligi   sababli,   uni
tashlang.
9.   Pick   qirrasi   0-7:   Hech   qanday   sikl   hosil   bo’lmaydi,   uni   qo’shing.  
 
10.   1-2 qirraini tanlang:   Ushbu qirra qo’shilishi  siklga olib kelganligi sababli, uni
tashlang.
11.   Pick   qirrasi   3-4:   Hech   qanday   sikl   hosil   bo’lmaydi,   uni   qo’shing.  
 
26 Kiritilgan   qirralarning   soni   (V   -   1)   teng   bo’lganligi   sababli,   algoritm   shu   erda
to’xtaydi.
Kraskalning   minimal   xarajat   daraxtini   topish   algoritmi   greedy   yondashuvdan
foydalanadi.   Ushbu   algoritm   grafni   o’rmon   va   har   bir   tugunni   alohida   daraxt
sifatida   ko’rib   chiqadi.   Daraxt   boshqasiga   ulanadi,   agar   u   barcha   mavjud
variantlar orasida eng kam xarajatga ega bo’lsa va MOD xususiyatlarini buzmasa.
Og’irligi yo’naltirilmagan graf berilgan.   Ushbu grafning barcha uchlarini bir-biriga
bog’laydigan   va   shu   bilan   birga   barcha   mumkin   bo’lganlarning   eng   kichik
og’irligiga   (ya’ni   qirra   og’irliklar   yig’indisiga)   ega   bo’lgan   shunday   pastki
daraxtini   topish   talab   qilinadi.   Bunday   pastki   daraxt   minimal   kenglikdagi   daraxt
yoki oddiy minimal kenglikdagi daraxt deb ataladi.
Bu erda biz minimal kenglikdagi daraxtlar bilan bog’liq bir nechta muhim faktlarni
ko’rib chiqamiz, keyin biz Kraskal algoritmini eng oddiy amalga oshirishda ko’rib
chiqamiz.
Minimal oraliq xususiyatlar
 Agar   barcha   qirralarning   og’irligi   har   xil   bo’lsa,   minimal   kenglik
daraxti   noyobdir .   Aks   holda,   bir   nechta   minimal   oraliqlar   bo’lishi   mumkin
(konkret algoritmlar odatda mumkin bo’lgan oraliqlardan biri bilan yakunlanadi).
 Minimal   skelet   ham   qirra   og’irliklarining   minimal   mahsulotiga   ega   bo’lgan
skeletdir.
(buni   isbotlash   oson,   barcha   qirralarning   og’irliklarini   ularning   logarifmlari   bilan
almashtirish kifoya)
 Minimal   skelet,   shuningdek,   eng   og’ir   qirraining   minimal   og’irligi   bo’lgan
skeletdir .
(bu bayonot Kraskal algoritmining haqiqiyligidan kelib chiqadi)
 Maksimal   og’irlikdagi   skelet   minimal   og’irlikdagi   skeletga   o’xshash   tarzda
qidiriladi, barcha qirralarning belgilarini qarama-qarshi tomonlarga o’zgartirish va
skeletning minimal algoritmlaridan birini bajarish kifoya.
27  Eng oddiy amalga oshirish
Algoritmning amaliy qismi.
Kraskal algoritmida biz eng kam og’irlikdagi qirralardan boshlaymiz va maqsadga
erishilgunga   qadar   qirralarni   qo’shishni   davom   ettiramiz.   Kraskal   algoritmini
amalga oshirish bosqichlari quyidagilardan iborat:
o Birinchidan, barcha qirralarni past og’irlikdan balandgacha tartiblang.
o Endi,   eng   kam   og’irlikdagi   qirrasini   oling   va   uni   yoyilgan   daraxtga
qo’shing.   Agar qo’shiladigan qirra sikl yaratsa, qirradan voz keching.
o Biz   barcha   tugunlarga   yetguncha   qirralarni   qo’shishni   davom   eting   va
minimal kenglikdagi daraxt yaratiladi.
Kraskal algoritmining ilovalari -
o Kraskal   algoritmi   shaharlar   orasidagi   elektr   simlarini   joylashtirish   uchun
ishlatilishi mumkin.
o U LAN ulanishlarini o’rnatish uchun ishlatilishi mumkin.
Kraskal algoritmiga misol. 
Keling,   misol   yordamida   Kraskal   algoritmining   ishlashini   ko’rib   chiqaylik.   Misol
yordamida Kraskalning algoritmini tushunish osonroq bo’ladi.
Aytaylik, vaznli graf -
28 Yuqoridagi grafning qirralarining og’irligi quyidagi jadvalda berilgan -
Qirra AB AC AD AE Miloddan avvalgi CD DE
Og’irligi 1 7 10 5 3 4 2
Endi yuqorida keltirilgan qirralarni og’irliklarining o’sish tartibida tartiblang.
           
Qirra AB DE Miloddan avvalgi CD AE AC AD
Og’irligi 1 2 3 4 5 7 10
Keling, minimal kenglikdagi daraxtni qurishni boshlaylik.
1-qadam -   Birinchidan, MODga   og’irligi   1 bo’lgan   AB   qirraini qo’shing.
29 2-qadam   -   MOD   ga   og’irligi   2   bo’lgan   DE   qirrasini   qo’shing,   chunki   u   siklni
yaratmaydi.
3-qadam   -   MOD   ga   og’irligi   3   bo’lgan   BC   qirraini   qo’shing,   chunki   u   hech
qanday sikl yoki halqa yaratmaydi.
30 4-qadam   -   Endi   MOD   ga   og’irligi   4   bo’lgan   qirra   diskni   tanlang,   chunki   u   siklni
tashkil etmaydi.
5-qadam   -   Shundan   so’ng,   og’irligi   5   bo’lgan   AE   qirrasini   tanlang.   Ushbu   qirra,
shu jumladan, sikl hosil qiladi, shuning uchun uni tashlang.
6-qadam   -   Og’irligi   7   bo’lgan   AC   qirraini   tanlang.   Ushbu   qirra   qo’shilishi   siklni
yaratadi, shuning uchun uni tashlang.
7-qadam   –   10   og’irligi   bo’lgan   AD   qirrasini   tanlang.   Bu   qirra   qo’shilganda   sikl
ham hosil bo’ladi, shuning uchun uni tashlab yuboring.
     
31 Shunday   qilib,   Kraskal   algoritmidan   foydalangan   holda   berilgan   vaznli   grafdan
olingan yakuniy minimal chegara daraxti -
MOD narxi = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.
Endi, yuqoridagi daraxtning qirralari soni  minus 1 tugunlar soniga teng. Shunday
qilib, algoritm shu erda to’xtaydi.
Algoritm
1. 1   -   qadam:   F   o rmonini   shunday   yaratingki,   grafning   har   bir   cho qqisi   alohidaʻ ʻ
daraxt bo lsin.	
ʻ    
2. 2   - qadam: Grafning barcha qirralarini o’z ichiga olgan E to’plamini yarating.    
3. 3   - qadam:   4     va     5 -   qadamlarni takrorlang     ,     E BO’SH EMAS va F oraliq emas      
4. 4   - qadam: Minimal og’irlik bilan E ning qirraini olib tashlang    
5. 5   -   qadam:   Agar   4   -bosqichda   olingan   qirra       ikki   xil   daraxtni   bog’lasa,   uni   F
o’rmoniga qo’shing.      
6. (ikkita daraxtni bitta daraxtga birlashtirish       uchun).
7. BOSHQA    
8. Qirraini tashlang    
9. 6-   qadam: TUGASH    
Kraskal algoritmi uchun C++ dasturi
32 Kraskal   algoritmining   C++   tilida   union-find   algoritmi   yordamida   amalga
oshirilishi quyida keltirilgan.   Bu C++ Kraskal algoritmining manba kodi: 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const  int  MAX  =   1e6 - 1 ;
int  root[MAX];
const  int  nodes  =   4 , edges  =   5 ;
pair  < long   long , pair < int ,  int >   >  p[MAX];
int  parent( int  a)   //   berilgan tugunning ota-onasini toping
{
     while (root[a]  !=  a)
    {
        root[a]  =  root[root[a]];
        a  =  root[a];
    }
     return  a;
}
void   union_find( int   a,   int   b)   //   berilgan   ikkita   tugun   bir   xil   "birlashmada"
yoki yo'qligini tekshiring
{
     int  d  =  parent(a);
     int  e  =  parent(b);
    root[d]  =  root[e];
}
33 long   long  Kraskal()
{
     int  a, b;
     long   long  cost, minCost  =   0 ;
     for ( int  i  =   0  ; i  <  edges ;  ++ i)
    {
        a  =  p[i] . second . first;
        b  =  p[i] . second . second;
        cost  =  p[i] . first;
           if (parent(a)  !=  parent(b)) //   faqat qirrani tanlang, agar u sikl yaratmasa (ya'ni,
uni tashkil etuvchi ikkita tugun turli xil ildiz tugunlariga ega)
        {
            minCost  +=  cost;
            union_find(a, b);
        }
    }
     return  minCost;
}
int  main()
{
     int  x, y;
     long   long  weight, cost, minCost;
     for ( int  i  =   0 ;i  <  MAX; ++ i) //   massiv guruhlarini ishga tushiring
    {
        root[i]  =  i;
    }
    p[ 0 ]  =  make_pair( 10 , make_pair( 0 ,  1 ));
    p[ 1 ]  =  make_pair( 18 , make_pair( 1 ,  2 ));
34     p[ 2 ]  =  make_pair( 13 , make_pair( 2 ,  3 ));
    p[ 3 ]  =  make_pair( 21 , make_pair( 0 ,  2 ));
    p[ 4 ]  =  make_pair( 22 , make_pair( 1 ,  3 ));
    sort(p, p  +  edges);   //   qirralarning qatorini tartiblang
    minCost  =  Kraskal();
    cout  <<   "Minimum cost is: " <<  minCost  <<  endl;
     return   0 ;
}
Kraskal algoritmining murakkabligi.
Keling, Kraskal algoritmining vaqt murakkabligini ko’rib chiqaylik.
1. #include   <iostream>        
2. #include   <algorithm>        
3. using   namespace   std;        
4. const   int   MAX   =   1e4   +   5;        
5. int   id [MAX],   nodes,   edges;        
6. pair   < long   long ,   pair< int ,   int >   >   p[MAX];        
7. void   init   ()        
8. {        
9.         for  ( int   i   =   0; i   <   MAX; ++i)        
10.                 id[i]   =   i;        
11. }            
12. int   root   ( int   x)        
13. {        
14.         while (id[x]!   =   x)        
15.         {        
16.                 id[x]   =   id[id[x]];        
17.                 x   =   id[x];        
18.         }        
35 19.         return   x;        
20. }            
21. void   union1( int   x,   int   y)        
22. {        
23.         int   p   =   root(x);        
24.         int   q   =   root(y);        
25.         id[p]   =   id[q];        
26. }          
27. long   long   Kraskal (pair< long   long ,   pair< int ,   int >   >   p[])        
28. {        
29.         int   x,   y;        
30.         long   long   cost,   minimumCost   =   0;        
31.         for ( int   i   =   0;i   <   edges;++i)        
32.         {        
33.                 x   =   p[i].second.first;        
34.                 y   =   p[i].second.second;        
35.                 cost   =   p[i].first;        
36.                 if (root(x)   !=   root(y))        
37.                 {        
38.                         minimumCost   +=   cost;        
39.                         union1(x,   y);        
40.                 }                
41.         }        
42.         return   minimumCost;        
43. }          
44. int   main   ()        
45. {        
46.         int   x,   y;        
47.         long   long   weight,   cost,   minimumCost;        
48.         Init   ();        
36 49.         cout   << "Enter   Nodes   and   edges" ;        
50.         c in   >>   nodes   >>   edges;        
51.         for  ( int   i   =   0; i   <   edges; ++i)        
52.         {        
53.                 cout<< "Enter   the   value   of   X,   Y   and   edges" ;        
54.         cin>>   x>>   y>>   weight;        
55.                 p[i]   =   make_pair (weight,   make_pair (x,   y));        
56.         }        
57.         s ort   (p,   p   +   edges);        
58.         minimumCost   =   Kraskal(p);        
59.         cout   << "Minimum   cost   is   " <<   minimumCost   <<   endl;        
60.         return   0;        
61. }          
Chiqish
Kraskal algoritmining vaqt murakkabligi O (E logE) yoki O (V logV), bu erda E -
qirralarning soni, V esa - uchlari soni.
37 Vaqt   murakkabligi:   O(ElogE)   yoki   O(ElogV).   Qirralarni   saralash   O(ELogE)
vaqtni   oladi.   Saralashdan   so’ng   biz   barcha   qirralarni   takrorlaymiz   va   union-find
algoritmini   qo’llaymiz.   Topish   va   birlashtirish   operatsiyalari   eng   ko’p   O(LogV)
vaqtni  olishi  mumkin.   Shunday qilib, umumiy murakkablik O (ELogE  + ELogV)
vaqtidir.   E qiymati ko’pi bilan O (V   2
) bo’lishi  mumkin, shuning uchun O(LogV)
O(LogE) bir xil bo’ladi.   Shuning uchun umumiy vaqt murakkabligi O(ElogE) yoki
O(ElogV) ga teng.
 
38 39 Xulosa.
Xulosa   o’rnida   shuni   aytish   mumkinki,   graflar   dasturlashning   yangi
boshlanuvchilar   uchun   eng   qiyin   sohalaridan   biri   hisoblanadi.   Buning   sababi,
birinchi   navbatda,   graflardagi   ma’lumotlar   tuzilmalari   va   algoritmlari   haqidagi
savollar   yechimni   qanday   davom   ettirish   haqida   juda   aniq   emas.   Faqat   qattiq
amaliyot orqali algoritm bo’yicha bilimlarini oshirish mumkin.   Ko’rinib turibdiki,
graflar bilan ishlatiladigan eng mashhur algoritmlardan biri bu grafni minimal vaqt
ichida   kesib   o’tish   va   undan   minimal   o’tish   daraxtini   ishlab   chiqaradigan
algoritmlardir.   Graflarni   o’tkazish   uchun   minimal   oraliq   daraxtni   Kraskal
algoritmi   yordamida ishlab chiqarish mumkin.
Bu   muammolarni   hal   qilish   uchun   graflardan   foydalanganda   o’rganish
mumkin   bo’lgan   eng   oson   algoritmlardan   biridir.   Minimal   kenglikdagi   daraxtlar
qirralarning   sonini   katta   darajada   kamaytirishga   yordam   beradi,   shunda   faqat
minimal   qirralar   ko’rsatiladi.   Bu,   o’z   navbatida,   graflar   yordamida   yechilishi
mumkin   bo’lgan   turli   xil   savollarni   yechishda   qo’llaniladi.   Har   qanday   yangi
boshlanuvchilar   uchun   haqiqiy   qiyinchilik   -   graflardan   muammoning   yechimini
topishda   foydalanish   mumkinligini   tushunish   va   ularning   ustunlari   va   qirralarini
o’z foydasiga qanday boshqarishni tushunishdir.
Biz  ko’rib  chiqqan   kraskal   algoritmi  minimal  oraliq  daraxtini  topish   uchun
qo’llaniladi.Bu   algoritm   greedy   sifatida   tanilgan.Bu   algoritmning   ishlash   prinspi
prima   algoritmidan   farqli   o’laroq   tugunni   tanlash   emas,   balki   eng   kichik   vaznli
qirra(ya’ni yoy) ni tanlab, daraxtga qo’shish orqali amalga oshiriladi.Qirra qo’shish
jarayonida   bitta   narsaga   e’tibor   berish   kerak,   ya’ni   qo’shilgan   qirra   daraxtda   sikl
paydo   qilmaslik   kerak.Bu   jarayon   barcha   tugunlar   o’zaro   bog’langunga   qadar
davom   etadi.Kraskal   algoritmi   shaharlararo   elektr   liniyalarini   o’rnatishda
ishlatiladi.
40 Foydanilgan adabiyotlar.
1.M.O’.   ASHUROV,   SH.A.SATTAROVA,   SH.U.USMONQULOV,
„ALGORITMLAR“,   «Fan   va   texnologiya»   nashriyoti,   2018.
2.H.To‘rayev,“Kombinatorika   va   graflar   nazariyasi”,   “Ilm   ziyo”,   2009,
3.Akbaraliyev   B.B.,   Yusupova   Z.Dj,   “MA LUMOTLAR   TUZILMASI   VA‟
ALGORITMLAR”, Toshkent 2013                                                               
4.Toirov   Sh.A.,   Raximov   R.T.,   Karimov   M.M,   “ALGORITMGA   KIRISH”
fanidan   laboratoriya   ishlarini   bajarish   bo’yicha   USLUBIY   KO’RSATMA”,
Samarqand 2015                                                                                      
5.Xayitmatov   O‘.T,   Inogomjonov   E.E.,   Sharipov   B.A.,   Ro’zmetova   N.,
Rahimboboeva   D,”   MA’LUMOTLAR   TUZILMASI   VA   ALGORITMLARI”,
Toshkent – 2011                                                                                               
6.Л.И.Домнин, “ЭЛИМЕНТЫ ТЕОРИИ ГРАФОВ”, “Пенза Издательство        
Пензенского государственного университета“,2007                                      
7.Никлаус Вирт,”Алгоритмы и структуры данных Новая версия для Оберона 
+CD“, Москва ,2010  
Foydalanilgan internet saytlar
8.https://kursovik.com/programming/320372.html
9.http://aliev.me/runestone/Graphs/PrimsSpanningTreeAlgorithm.html
10.http://www.hpcc.unn.ru/?dir=836
11.https://brestprog.by/topics/MOD/
12. https://wikipedia.uz                                                       
13.https://evileg.com/ru/post/524/                                   
14.http://www.mkurnosov.net/                                                              
41 42

“KRASKAL ALGORITMI” MAVZUSIDA TAYYORLAGAN Mundarija Kirish. ............................................................................................................................................................................. 2 Kraskal algoritmi. ............................................................................................................................................................ 3 Kraskal algoritmining tavsifi. ......................................................................................................................................... 7 Algoritmning psevdokodi. ............................................................................................................................................ 16 Kraskalning minimal kengayuvchi daraxt algoritmi. .................................................................................................... 20 Algoritmning amaliy qismi. .......................................................................................................................................... 28 Kraskal algoritmining murakkabligi. ............................................................................................................................ 35 Xulosa. .......................................................................................................................................................................... 40 Foydanilgan adabiyotlar. ............................................................................................................................................... 41 1

Kirish. Kurs ishining o’rganish ob’ekti Kraskal algoritmini amalga oshirish edi. Ishning maqsadlari quyidagilar edi: 1)kraskal algoritmi, uning tarixi bilan tanishish; 2)minimal kenglikdagi daraxtni qurish algoritmini amalga oshirish; 3)algoritmning murakkabligini tahlil qilish; 4)algoritmni sinash. Bog’langan vaznli grafning minimal oraliq daraxti (MOD) uning bog’langan pastki grafigi bo’lib, u asl daraxtning barcha uchlari va uning ba’zi qirralaridan iborat bo’lib, qirralarning og’irliklarining yig’indisi maksimal mumkin. Agar asl graf uzilgan bo’lsa, unda quyida tavsiflangan protsedura uning har bir ulangan komponentiga navbat bilan qo’llanilishi mumkin va shu bilan ushbu komponentlar uchun minimal oraliq daraxtlarni olish mumkin. Kraskal algoritmi (yoki Kraskal algoritmi) vaznli bog langan yo naltirilmagan graf uchun minimal oraliqli daraxtniʻ ʻ qurish algoritmidir. Algoritm birinchi marta 1956 yilda Jozef Kraskal tomonidan tasvirlangan. Kraskal algoritmi bir vaqtning o’zida bir nechta bog’langan komponentlar uchun daraxt qurishi mumkin, ular hal qilish jarayonida bitta bog’langan daraxtga birlashtiriladi. To’liq graf qirralarning ro’yxati bilan berilgan. Yugurishdan oldin qirralarning ro’yxati uzunlik bo’yicha o’sish tartibida tartiblanadi. Har bir bosqichda qirralarning ro’yxati ko’rib chiqiladi, oldingi bosqichdagi yechimga kiritilganidan keyingi qirraidan boshlab, eritma ichiga kiritilgan qirralar bilan sikl hosil qilmaydigan qirra pastki daraxtga qo’shiladi. qurilish ishlari olib borilmoqda. Daraxtning minimal uzunligini topish muammosi ko’pincha shunga o’xshash sharoitda yuzaga keladi: n ta shahar bor, ular orqali siz istalgan shahardan boshqasiga (to’g’ridan-to’g’ri yoki boshqa shaharlar orqali) borishingiz mumkin bo’lgan marshrutni yotqizishingiz mumkin. Yo’l haqi maksimal bo’lishi uchun shunday marshrutni topish talab qilinadi. Amalda Kraskal 2

algoritmi aviakompaniyalar tomonidan bir yo’nalishdan ikkinchisiga eng qisqa havo yo’lini topishda qo’llaniladi. Kraskal algoritmi. Kraskal algoritmi bog’langan vaznli graf uchun minimal oraliq daraxtini topish uchun ishlatiladi. Algoritmning asosiy maqsadi biz grafning har bir tugunini kesib o’tishimiz mumkin bo’lgan qirralarning pastki to’plamini topishdir. U global optimalga e’tibor qaratish o’rniga har bir bosqichda optimal echim topadigan greedy yondashuvga amal qiladi. Kraskal algoritmi bu grafning MODni topish uchun boshqa mantiqdan foydalanadigan yana bir mashhur minimal oraliqli daraxt algoritmi. Kraskal algoritmi tugundan boshlash o’rniga, barcha qirralarni past og’irlikdan yuqoriga saralaydi va siklni yaratadigan qirralarga e’tibor bermasdan, eng past qirralarni qo’shishda davom etadi. Kraskal algoritmi dastlab har bir tugunni o’z daraxtiga joylashtiradi, so’ngra bu daraxtlarni asta-sekin birlashtirib, har bir iteratsiyada qaysidir qirrada ikkita ma’lum daraxtni birlashtiradi. Algoritmni boshlashdan oldin barcha qirralarning vazni bo’yicha (kamaymaslik tartibida) tartiblanadi. Keyin birlashtirish jarayoni boshlanadi: barcha qirralar birinchisidan oxirgisiga (tartib tartibida) o’tkaziladi va agar joriy qirraning uchlari turli pastki daraxtlarga tegishli bo’lsa, u holda bu pastki daraxtlar birlashtiriladi va javobga qirra qo’shiladi. Barcha qirralarni sanab o’tish oxirida barcha tugunliklar bir xil pastki daraxtga tegishli bo’ladi va javob topiladi. Bizda quyidagi yo’naltirilmagan vaznli graf mavjud, grafning barcha tugunlarini o’z ichiga olgan pastki graf, ya’ni daraxt bo’lgan kengaytmali daraxt deb ataymiz va vazifa - qirralarining yig’indisi minimal bo’lgan bunday kengaygan daraxtni topishdir. Asl grafni qirralarsiz tasavvur qiling, endi siz barcha tugunlarni qandaydir tarzda bir-biriga bog’lashingiz kerak, shunda siz istalgan tugundan ikkinchisiga 3

o’tishingiz mumkin, natijada olingan grafda kiritilgan qirralarning og’irliklarining minimal mumkin bo’lgan yig’indisi bilan sikllarsiz ishlaydi. Ushbu algoritmning ishlash mexanizmi juda oddiy. Kirish qismida bo’sh subgraf mavjud bo’lib, biz uni potentsial minimal kenglikdagi daraxtga yakunlaymiz. Biz faqat bog’langan graflarni ko’rib chiqamiz, aks holda Kraskal algoritmini qo’llashda biz minimal kenglikdagi daraxtni emas, balki oddiygina o’rmonni olamiz.  Birinchidan, biz qirralarni og’irliklari bo’yicha kamaymaydigan tartibda saralaymiz.  Biz subgrafimizga qirra qo’shamiz i- ое , agar bu qirra ikki xil bog’langan komponentni bog’lasa, ulardan biri bizning subgrafimizdir. Ya’ni, har bir qadamda minimal og’irlik qirrasi qo’shiladi, uning bir uchi bizning subgrafimizda mavjud, ikkinchisi esa hali yo’q.  Algoritm o’z ishini subgrafimizning tugunlari to’plami asl grafning tugunlari to’plamiga to’g’ri kelgandan keyin yakunlaydi. Ushbu algoritm greedy deb ataladi, chunki har bir qadamda biz umuman optimal yechimga olib keladigan eng yaxshi variantni topishga harakat qilamiz. Muayyan misolni bosqichma-bosqich tahlil qilish. Quyda keltirilgan grafdan biz uning barcha qirralarini tartiblangan tartibda yozamiz, va biz ushbu qirralarni ro’yxatdagi skeletimizga qo’shishni boshlaymiz: 1) D <--> B; w = 2 2) D <--> C; w = 6 4

3) A <--> B; w = 7 4) A <--> C; w = 8 5) C <--> E; w = 9 6) D <--> F; w = 9 7) F <--> E; w = 10 8) B <--> C; w = 11 9) D <--> E; w = 11 1-qirra qo’shgandan keyin pastki chiziq 2 va 3 qirralarni qo’shgandan so’ng subgraph A <--> C Ko’rib turganingizdek, bizning kengaygan daraxtimizga qirra qo’shsangiz, sikl hosil bo’ladi, shuning uchun biz bu qirrani o’tkazib yuboramiz. Natijada, bizda quyidagi subgraf bor va siz sezganingizdek, biz barcha tugunlarni qirralar bilan minimal mumkin bo’lgan og’irliklar bilan birlashtirdik, ya’ni biz asl grafmiz uchun minimal oraliq daraxtini topdik. 5