DSA Kruskal algoritmi

Kruskal algoritmi

Kruskal algoritmi yo‘naltirilmagan grafda minimal qamrovchi daraxtni (MST) yoki minimal qamrovchi o‘rmonni topadi.

Bog‘lamli

Kruskal algoritmi topgan MST (yoki MST’lar) — barcha cho‘qqilarni (yoki imkon qadar ko‘p cho‘qqini) eng kichik umumiy qirra vazni bilan bog‘laydigan qirralar to‘plami.

Kruskal algoritmi MST’ga (yoki minimal qamrovchi o‘rmonga) qirralarni eng kichik qirra vaznli qirralardan boshlab qo‘shadi.

Sikl hosil qiladigan qirralar MST’ga qo‘shilmaydi. Yuqoridagi animatsiyada ular qizil rangda miltillovchi chiziqlar ko‘rinishida.

Kruskal algoritmi grafdagi barcha qirralarni tekshiradi, ammo eng uzun qirralar tekshirilishini kutib o‘tirmasligingiz uchun yuqoridagi animatsiya MST yoki minimal qamrovchi o‘rmon tayyor bo‘lganda to‘xtaydigan qilib yasalgan.

Grafda bittadan ortiq minimal qamrovchi daraxt bo‘lsa, bu minimal qamrovchi o‘rmon deb ataladi. Bu graf bog‘lamli bo‘lmaganda yuz beradi. Buni yuqoridagi animatsiyadagi belgilash katakchasi (checkbox) yordamida o‘zingiz sinab ko‘ring.

Prim algoritmidan farqli ravishda, Kruskal algoritmini bog‘lamli bo‘lmagan graflar uchun ham ishlatish mumkin, ya’ni u bittadan ortiq MST’ni topa oladi — biz buni minimal qamrovchi o‘rmon deb ataymiz.

Qirra sikl hosil qilish-qilmasligini aniqlash uchun Kruskal algoritmi ichida Union-Find yordamida sikllarni aniqlash usulidan foydalanamiz.

Qanday ishlaydi:

Grafdagi qirralarni qirra vazni bo‘yicha eng kichigidan eng kattasigacha saralang.
Eng kichik qirra vaznlisidan boshlab har bir qirra uchun:
1. Bu qirra joriy MST’da sikl hosil qiladimi?
  - Agar yo‘q bo‘lsa: qirrani MST qirrasi sifatida qo‘shing.

Qo‘lda bajarib ko‘rish

Keling, Kruskal algoritmini dasturlashga urinishdan oldin uning qadamma-qadam amallarini batafsil tushunib olish uchun uni quyidagi grafda qo‘lda bajarib ko‘raylik.

Dastlabki uchta qirra MST’ga qo‘shiladi. Bu uchta qirra eng kichik qirra vaznlariga ega va hech qanday sikl hosil qilmaydi:

C-E, vazni 2
D-E, vazni 3
A-B, vazni 4

Shundan so‘ng C-D qirrasini (qizil rangda ko‘rsatilgan) qo‘shib bo‘lmaydi, chunki u siklga olib keladi.

Kruskal algoritmi MST’ga qo‘shishga urinadigan keyingi to‘rtta qirra:

E-G, vazni 6
C-G, vazni 7 (qo‘shilmaydi)
D-F, vazni 7
B-C, vazni 8

C-G qirrasini (qizil rangda ko‘rsatilgan) MST’ga qo‘shib bo‘lmaydi, chunki u sikl hosil qiladi.

Ko‘rib turganingizdek, bu paytga kelib MST allaqachon yaratilgan, ammo Kruskal algoritmi barcha qirralar MST’ga qo‘shilishi mumkinligi tekshirib chiqilmaguncha ishlashda davom etadi.

Kruskal algoritmi MST’ga qo‘shishga urinadigan oxirgi uchta qirra eng katta qirra vaznlariga ega qirralardir:

A-C, vazni 9 (qo‘shilmaydi)
A-G, vazni 10 (qo‘shilmaydi)
F-G, vazni 11 (qo‘shilmaydi)

Bu qirralarning har biri MST’da sikl hosil qiladi, shuning uchun ularni qo‘shib bo‘lmaydi.

Kruskal algoritmi endi o‘z ishini tugatdi.

Kruskal algoritmi biz hozirgina qo‘lda bajargan qadamlarni qanday bajarishini ko‘rish uchun quyidagi simulyatsiyani ishga tushiring.

Eslatma: Kruskal algoritmi grafdagi barcha qirralarni tekshirsa ham, qo‘shib bo‘lmaydigan barcha qizil qirralarga qarab o‘tirmasligimiz uchun ushbu sahifaning yuqorisidagi animatsiya oxirgi qirra MST’ga yoki minimal qamrovchi o‘rmonga qo‘shilishi bilanoq to‘xtaydi.

Bu mumkin, chunki bog‘lamli grafda faqat bitta MST bo‘ladi va MST’dagi qirralar soni grafdagi cho‘qqilar sonidan bitta kam bo‘lganda (\(V-1\)) qidiruvni to‘xtatish mumkin. Animatsiyamizdagi bog‘lamli bo‘lmagan grafda ikkita MST bor va MST’lar jami \(V-2\) ta qirra hajmiga yetganda algoritm to‘xtaydi.

Kruskal algoritmini amalga oshirish

Kruskal algoritmi minimal qamrovchi daraxtni (MST) yoki minimal qamrovchi o‘rmonni topishi uchun Graph sinfini yaratamiz. Keyinchalik yuqoridagi misoldagi grafni yaratish va unda Kruskal algoritmini ishga tushirish uchun ushbu Graph sinfi ichidagi metodlardan foydalanamiz.

class Graph:
    def __init__(self, size):
        self.size = size
        self.edges = []  # For storing edges as (weight, u, v)
        self.vertex_data = [''] * size  # Store vertex names

    def add_edge(self, u, v, weight):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.edges.append((weight, u, v))  # Add edge with weight
            
    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

8- va 12-qatorlar: u, v va vertex kirish argumentlari indeks qiymatlarining mumkin bo‘lgan oralig‘ida ekanligini tekshiradi.

Kruskal algoritmida Union-Find yordamida sikllarni aniqlash uchun Graph sinfi ichida find va union degan ikkita metod ham aniqlanadi:

    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

15–18-qatorlar: find metodi cho‘qqining ildizini rekursiv ravishda topish uchun parent massividan foydalanadi. Har bir cho‘qqi uchun parent massivi shu cho‘qqining otasiga ko‘rsatkich (indeks) saqlaydi. find metodi parent massivida o‘zini o‘zi ko‘rsatadigan cho‘qqiga yetib kelganda ildiz cho‘qqi topiladi. find metodi va parent massivi kruskals_algorithm metodi ichida qanday ishlatilishini bilish uchun o‘qishda davom eting.

20–29-qatorlar: MST’ga qirra qo‘shilganda union metodi ikkita daraxtni birlashtirish (union) uchun parent massividan foydalanadi. rank massivi har bir ildiz cho‘qqi uchun daraxt balandligining taxminiy bahosini saqlaydi. Ikki daraxt birlashtirilganda rangi (rank) kichikroq bo‘lgan ildiz boshqa daraxt ildiz cho‘qqisining bolasiga aylanadi.

Kruskal algoritmi Graph sinfi ichidagi metod sifatida quyidagicha amalga oshiriladi:

    def kruskals_algorithm(self):
        result = []  # MST
        i = 0 # edge counter

        self.edges = sorted(self.edges, key=lambda item: item[2])

        parent, rank = [], []

        for node in range(self.size):
            parent.append(node)
            rank.append(0)

        while i < len(self.edges):
            u, v, weight = self.edges[i]
            i += 1

            x = self.find(parent, u)
            y = self.find(parent, v)
            if x != y:
                result.append((u, v, weight))
                self.union(parent, rank, x, y)

        print("Edge \tWeight")
        for u, v, weight in result:
            print(f"{self.vertex_data[u]}-{self.vertex_data[v]} \t{weight}")

35-qator: Kruskal algoritmi qirralarni MST’ga qo‘shishga urinishni boshlashidan oldin qirralar saralangan bo‘lishi kerak.

40–41-qatorlar: parent va rank massivlari initsializatsiya qilinadi. Boshida har bir cho‘qqi o‘zining ildizi hisoblanadi (parent massividagi har bir element o‘zini ko‘rsatadi) va har bir cho‘qqining balandligi yo‘q (rank massividagi 0 qiymatlar).

44–45-qatorlar: Eng kichik qirrani tanlang va keyingi iteratsiyada to‘g‘ri qirra tanlanishi uchun ini bittaga oshiring.

47–51-qatorlar: Agar joriy qirraning ikki uchidagi u va v cho‘qqilarining ildizlari (x va y) turlicha bo‘lsa, demak yangi qirra sikl hosil qilmaydi va daraxtlar birlashtiriladi. Daraxtlarni birlashtirish uchun joriy qirra result massiviga qo‘shiladi va daraxtlar to‘g‘ri birlashtirilishini, ya’ni hosil bo‘lgan birlashgan daraxtda faqat bitta ildiz cho‘qqi bo‘lishini ta’minlash uchun union metodini ishga tushiramiz.

Endi yuqoridagi "Qo‘lda bajarib ko‘rish" bo‘limidagi grafni yaratamiz va unda Kruskal algoritmini ishga tushiramiz:

Misol

Python:

class Graph:
    def __init__(self, size):
        self.size = size
        self.edges = []  # For storing edges as (weight, u, v)
        self.vertex_data = [''] * size  # Store vertex names

    def add_edge(self, u, v, weight):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.edges.append((u, v, weight))  # Add edge with weight
            
    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

    def kruskals_algorithm(self):
        result = []  # MST
        i = 0  # edge counter

        self.edges = sorted(self.edges, key=lambda item: item[2])

        parent, rank = [], []

        for node in range(self.size):
            parent.append(node)
            rank.append(0)

        while i < len(self.edges):
            u, v, weight = self.edges[i]
            i += 1
            
            x = self.find(parent, u)
            y = self.find(parent, v)
            if x != y:
                result.append((u, v, weight))
                self.union(parent, rank, x, y)

        print("Edge \tWeight")
        for u, v, weight in result:
            print(f"{self.vertex_data[u]}-{self.vertex_data[v]} \t{weight}")

g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')

g.add_edge(0, 1, 4)  #A-B,  4
g.add_edge(0, 6, 10) #A-G, 10
g.add_edge(0, 2, 9)  #A-C,  9
g.add_edge(1, 2, 8)  #B-C,  8
g.add_edge(2, 3, 5)  #C-D,  5
g.add_edge(2, 4, 2)  #C-E,  2
g.add_edge(2, 6, 7)  #C-G,  7
g.add_edge(3, 4, 3)  #D-E,  3
g.add_edge(3, 5, 7)  #D-F,  7
g.add_edge(4, 6, 6)  #E-G,  6
g.add_edge(5, 6, 11) #F-G, 11

print("Kruskal's Algorithm MST:")
g.kruskals_algorithm()

O‘zingiz sinab ko‘ring »

Kruskal algoritmining vaqt murakkabligi

Vaqt murakkabligi nima ekanligi haqida umumiy tushuntirish uchun ushbu sahifaga tashrif buyuring.

Grafimizdagi qirralar soni \(E\) bo‘lsa, Kruskal algoritmining vaqt murakkabligi quyidagiga teng

\[ O( E \cdot log{E} ) \]

Bunday vaqt murakkabligi hosil bo‘lishining sababi — Kruskal algoritmi MST’ga qirralar qo‘shishni boshlashidan oldin qirralar saralanishi kerak. Quick Sort yoki Merge Sort kabi tezkor algoritmdan foydalanish faqat shu saralashning o‘zi uchun \( O( E \cdot log{E} ) \) vaqt murakkabligini beradi.

Qirralar saralangach, ularning barchasi sikl hosil qilish-qilmasligini aniqlash uchun birma-bir tekshiriladi va agar sikl hosil qilmasa, MST’ga qo‘shiladi.

find metodi yordamida sikl hosil bo‘lish-bo‘lmasligini tekshirish, so‘ngra union metodi yordamida qirrani MST’ga qo‘shish ko‘p ishdek tuyulsa-da, buni baribir bitta amal deb qarash mumkin. Buni bitta amal deb hisoblashimiz mumkinligining sababi shundaki, u taxminan o‘zgarmas vaqt oladi. Ya’ni graf kattalashgani sari bu amal oladigan vaqt juda kam o‘sadi, shuning uchun u aslida umumiy vaqt murakkabligiga hissa qo‘shmaydi.

Kruskal algoritmining vaqt murakkabligi faqat qirralar soni \(E\) ga bog‘liq ravishda o‘zgargani uchun u, ayniqsa, qirralar soni \(E\) va cho‘qqilar soni \(V\) orasidagi nisbat nisbatan kichik bo‘lgan siyrak graflarda tez ishlaydi.

W3Schools Pathfinder

Yutuqlaringizni kuzating – bu bepul!

Ro'yxatdan o'tish Kirish