DSA Prim algoritmi

Prim algoritmi

Prim algoritmi bog‘lamli va yo‘naltirilmagan grafda minimal qamrovchi daraxtni (MST) topadi.

Prim algoritmi topgan MST — grafdagi barcha cho‘qqilarni qirra vaznlarining eng kichik yig‘indisi bilan bog‘laydigan qirralar to‘plami.

Prim algoritmi MST’ni topish uchun avval MST’ga tasodifiy cho‘qqini qo‘shadi. So‘ngra algoritm joriy MST’dan eng kichik vaznli qirra bilan bog‘langan cho‘qqini topadi va uni MST’ga qo‘shadi. Prim algoritmi barcha tugunlar MST’ga kiritilguncha shu ishni davom ettiradi.

Prim algoritmi ochko‘z (greedy) algoritm bo‘lib, minimal qamrovchi daraxtni yaratishning sodda usuliga ega.

Prim algoritmi ishlashi uchun barcha tugunlar bog‘langan bo‘lishi kerak. Bog‘lamli bo‘lmagan grafda MST’larni topish uchun uning o‘rniga Kruskal algoritmidan foydalanish mumkin. Kruskal algoritmi haqida keyingi sahifada o‘qishingiz mumkin.

Qo‘lda bajarib ko‘rish

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

Prim algoritmi minimal qamrovchi daraxtni (MST) tasodifiy cho‘qqidan o‘stira boshlaydi, ammo bu namoyish uchun boshlang‘ich cho‘qqi sifatida A cho‘qqisi tanlangan.

A cho‘qqisidan MST eng kichik vaznli qirra bo‘ylab o‘sadi. Shunday qilib, endi A va D cho‘qqilari minimal qamrovchi daraxtga tegishli cho‘qqilar guruhiga kiradi.

Prim algoritmining MST’dagi qirralarni o‘stirishida parents massivi markaziy o‘rin tutadi.

Ayni paytda parents massivi quyidagicha ko‘rinadi:

parents = [-1,  0, -1,  0,  3,  3, -1, -1]
#vertices [ A,  B,  C,  D,  E,  F,  G,  H]

Boshlang‘ich cho‘qqi bo‘lgan A cho‘qqisining otasi yo‘q, shuning uchun uning qiymati -1. D cho‘qqisining otasi A, shu sababli D’ning ota qiymati 0ga teng (A cho‘qqisi 0-indeksda joylashgan). B’ning otasi ham A, D esa E va F’ning otasi.

parents massivi MST’ning daraxt tuzilmasini saqlashga yordam beradi (cho‘qqining faqat bitta otasi bo‘lishi mumkin).

Shuningdek, sikllarning oldini olish va hozirda qaysi cho‘qqilar MST’da ekanini kuzatib borish uchun in_mst massividan foydalaniladi.

Hozirda in_mst massivi quyidagicha ko‘rinadi:

 in_mst = [ true, false, false,  true, false, false, false, false]
#vertices [    A,     B,     C,     D,     E,     F,     G,     H]

Prim algoritmining keyingi qadami MST tarkibiga yana bitta cho‘qqi qo‘shishdan iborat va bunda joriy MST tugunlari A va D’ga eng yaqin cho‘qqi tanlanadi.

A-B va D-F qirralarining ikkalasi ham bir xil eng kichik 4 qirra vazniga ega bo‘lgani uchun keyingi MST cho‘qqisi sifatida B yoki F’ni tanlash mumkin. Bu namoyish uchun keyingi MST cho‘qqisi sifatida B’ni tanlaymiz.

Ko‘rib turganingizdek, E’ga boradigan MST qirrasi avval D cho‘qqisidan kelgan edi, endi esa B cho‘qqisidan keladi, chunki 6 vaznli B-E qirrasi 7 vaznli D-E qirrasidan kichikroq. MST daraxt tuzilmasida (va parents massivida) E cho‘qqisining faqat bitta otasi bo‘lishi mumkin, shuning uchun B-E va D-E ikkalasi bir vaqtda E’ga boradigan MST qirralari bo‘la olmaydi.

MST’dagi keyingi cho‘qqi — C, chunki 3 vaznli B-C qirrasi joriy MST cho‘qqilaridan chiquvchi eng kichik vaznli qirra.

C cho‘qqisi MST’ga kiritilgach, ushbu MST cho‘qqisidan MST’dan tashqaridagi cho‘qqilarga boradigan kichikroq vaznli qirralar bor-yo‘qligini aniqlash uchun C’dan chiquvchi qirralar tekshiriladi. C-E qirrasining vazni (3) oldingi B-E MST qirrasinikidan (6) kichikroq, C-H qirrasi esa 2 qirra vazni bilan MST’ga kiritiladi.

MST’ga keyingi kiritiladigan cho‘qqi — H, chunki u eng kichik 6 qirra vazniga ega; parents massivida H cho‘qqisi G cho‘qqisining otasiga aylanadi.

MST’ga keyingi kiritiladigan cho‘qqi E yoki F bo‘ladi, chunki ikkalasiga ham boradigan qirra vazni eng kichik: 4.

Bu namoyish uchun MST’ga keyingi kiritiladigan cho‘qqi sifatida E cho‘qqisini tanlaymiz.

MST’ga qo‘shiladigan keyingi va oxirgi ikkita cho‘qqi — F va G. F’ga boradigan MST qirrasi D-F, G’ga boradigani esa E-G, chunki bu qirralar joriy MST’dan chiquvchi eng kichik vaznli qirralardir.

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

Prim algoritmini amalga oshirish

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

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

    def add_edge(self, u, v, weight):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.adj_matrix[u][v] = weight
            self.adj_matrix[v][u] = weight  # For undirected graph

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

3–5-qatorlar: Dastlab qo‘shnilik matritsasi bo‘sh, ya’ni grafda qirralar yo‘q. Shuningdek, boshida cho‘qqilarning nomlari ham yo‘q.

7–10-qatorlar: add_edge metodi yo‘naltirilmagan grafga qirra vazni qiymati bilan qirra qo‘shish uchun mo‘ljallangan.

12–14-qatorlar: add_vertex_data metodi cho‘qqilarga nom berish uchun ishlatiladi, masalan, 'A' yoki 'B'.

Graf yaratish uchun tuzilma tayyor bo‘lgach, Prim algoritmini Graph sinfi ichidagi metod sifatida amalga oshirishimiz mumkin:

    def prims_algorithm(self):
        in_mst = [False] * self.size
        key_values = [float('inf')] * self.size
        parents = [-1] * self.size

        key_values[0] = 0  # Starting vertex

        print("Edge \tWeight")
        for _ in range(self.size):
            u = min((v for v in range(self.size) if not in_mst[v]), key=lambda v: key_values[v])

            in_mst[u] = True

            if parents[u] != -1:  # Skip printing for the first vertex since it has no parent
                print(f"{self.vertex_data[parents[u]]}-{self.vertex_data[u]} \t{self.adj_matrix[u][parents[u]]}")

            for v in range(self.size):
                if 0 < self.adj_matrix[u][v] < key_values[v] and not in_mst[v]:
                    key_values[v] = self.adj_matrix[u][v]
                    parents[v] = u

17-qator: in_mst massivi hozirda qaysi cho‘qqilar MST’da ekanligi holatini saqlaydi. Dastlab cho‘qqilarning hech biri MST tarkibida emas.

18-qator: key_values massivi MST cho‘qqilaridan MST’dan tashqaridagi har bir cho‘qqigacha bo‘lgan joriy eng qisqa masofani saqlaydi.

19-qator: MST qirralari parents massivida saqlanadi. Har bir MST qirrasi har bir cho‘qqi uchun ota indeksini saqlash orqali saqlanadi.

21-qator: Soddalik uchun va bu kod yuqoridagi "Qo‘lda bajarib ko‘rish" animatsiyasi/misolidagidek ishlashi uchun birinchi cho‘qqi (0-indeksdagi A cho‘qqisi) boshlang‘ich cho‘qqi qilib belgilangan. Indeksni 4ga o‘zgartirsangiz, Prim algoritmi E cho‘qqisidan ishga tushadi va bu ham xuddi shunday yaxshi ishlaydi.

25-qator: Hali MST tarkibiga kirmagan va kalit qiymati eng kichik bo‘lgan cho‘qqining indeksi topiladi. Ushbu Python kod qatorini yaxshiroq tushunish uchun min va lambda bo‘yicha tushuntirishlarni ko‘rib chiqing.

32–35-qatorlar: MST’ga yangi cho‘qqi qo‘shilgach (27-qator), kodning bu qismi yangi qo‘shilgan MST cho‘qqisidan MST’dan tashqaridagi boshqa cho‘qqilarga ularning kalit qiymatlarini kamaytira oladigan qirralar paydo bo‘lgan-bo‘lmaganini tekshiradi. Agar shunday bo‘lsa, key_values va parents massivlari mos ravishda yangilanadi. Buni animatsiyada yangi cho‘qqi MST’ga qo‘shilib, faol (joriy) cho‘qqiga aylanganda aniq ko‘rish mumkin.

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

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

    def add_edge(self, u, v, weight):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.adj_matrix[u][v] = weight
            self.adj_matrix[v][u] = weight  # For undirected graph

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

    def prims_algorithm(self):
        in_mst = [False] * self.size
        key_values = [float('inf')] * self.size
        parents = [-1] * self.size

        key_values[0] = 0  # Starting vertex

        print("Edge \tWeight")
        for _ in range(self.size):
            u = min((v for v in range(self.size) if not in_mst[v]), key=lambda v: key_values[v])

            in_mst[u] = True

            if parents[u] != -1:  # Skip printing for the first vertex since it has no parent
                print(f"{self.vertex_data[parents[u]]}-{self.vertex_data[u]} \t{self.adj_matrix[u][parents[u]]}")

            for v in range(self.size):
                if 0 < self.adj_matrix[u][v] < key_values[v] and not in_mst[v]:
                    key_values[v] = self.adj_matrix[u][v]
                    parents[v] = u

g = Graph(8)

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_vertex_data(7, 'H')

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

print("Prim's Algorithm MST:")
g.prims_algorithm()

Prim algoritmining vaqt murakkabligi

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

Grafimizdagi cho‘qqilar soni \(V\) bo‘lsa, Prim algoritmining vaqt murakkabligi quyidagiga teng

\[ O( V^2 ) \]

Bunday vaqt murakkabligi Prim algoritmi ichidagi ichma-ich joylashgan sikllar (ichida yana ikkita for sikli bo‘lgan bitta for sikli) tufayli hosil bo‘ladi.

Birinchi for sikli (24-qator) grafdagi barcha cho‘qqilarni aylanib chiqadi. Uning vaqt murakkabligi \(O(V)\).

Ikkinchi for sikli (25-qator) MST’ga kiritiladigan keyingi cho‘qqi bo‘lishi uchun MST’dan tashqaridagi eng kichik kalit qiymatli cho‘qqini topish maqsadida grafdagi barcha qo‘shni cho‘qqilarni aylanib chiqadi. Uning vaqt murakkabligi \(O(V)\).

MST’ga yangi cho‘qqi kiritilgach, uchinchi for sikli (32-qator) yangi qo‘shilgan MST cho‘qqisidan MST’dan tashqaridagi cho‘qqilarga boradigan, kalit qiymatlarni kamaytirishi va ota munosabatlarini yangilashi mumkin bo‘lgan chiquvchi qirralar bor-yo‘qligini aniqlash uchun boshqa barcha cho‘qqilarni tekshiradi. Uning vaqt murakkabligi ham \(O(V)\).

Vaqt murakkabliklarini birlashtirib, quyidagini olamiz:

\[ \begin{equation} \begin{aligned} O(V)\cdot (O(V)+O(V)) & = O(V)\cdot (2\cdot O(V)) \\ & = O(V\cdot 2\cdot V) \\ & = O(2\cdot V^2) \\\\ & = O(V^2) \end{aligned} \end{equation} \]

Kalit qiymatlarni boshqarish uchun bu yerdagidek massiv o‘rniga ustuvor navbat (priority queue) ma’lumotlar tuzilmasidan foydalanilsa, Prim algoritmining vaqt murakkabligini quyidagigacha kamaytirish mumkin:

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

Bu yerda \(E\) — grafdagi qirralar soni, \(V\) esa cho‘qqilar soni.

Prim algoritmining ustuvor navbatdan foydalanadigan bunday amalga oshirilishi siyrak graflar uchun eng yaxshisi. Agar har bir cho‘qqi boshqa cho‘qqilarning faqat bir nechtasi bilan bog‘langan bo‘lsa, graf siyrak hisoblanadi.