63 / 69

Prim's Algorithm

Prim algoritmi nima?

Prim algoritmi — bu berilgan bog'langan vaznli graf uchun minimal qamrovchi daraxtni (Minimum Spanning Tree - MST) topuvchi algoritmdir. U grafni qabul qilib, uning qirralari orasidan quyidagi shartlarni qanoatlantiruvchi qism-to'plamni aniqlaydi:

Grafning har bir cho'qqisini o'z ichiga oluvchi bitta daraxt hosil qiladi;
Ushbu grafdan tuzilishi mumkin bo'lgan barcha qamrovchi daraxtlar orasida qirralar vaznlari yig'indisi eng minimal bo'lishini ta'minlaydi.

Prim algoritmi qanday ishlaydi?

Prim algoritmi greedy (ochko'z) algoritmlar turkumiga kiradi. U har bir qadamda lokal optimal tanlovni amalga oshirib, yakunda global optimal natijaga erishishga intiladi.

Biz bitta ixtiyoriy cho'qqidan boshlaymiz va maqsadga erishguncha (barcha cho'qqilar qamrab olinguncha) daraxtga eng kam vaznga ega bo'lgan tutash qirralarni qo'shib boramiz.

Prim algoritmining asosiy qadamlari:

Minimal qamrovchi daraxtni tasodifiy tanlangan bitta cho'qqi bilan initsializatsiya qilish.
Daraxtdagi cho'qqilarni hali daraxtga qo'shilmagan yangi cho'qqilar bilan bog'lovchi barcha qirralarni ko'rib chiqish, ular orasidan eng kichik vaznli (minimal) qirrani topib, daraxtga qo'shish.
Minimal qamrovchi daraxt to'liq hosil bo'lguniga qadar (V - 1 ta qirra to'planguncha) 2-qadamni takrorlash.

Prim algoritmi misoli

Keling, Prim algoritmining 5 ta cho'qqidan iborat grafda ishlash jarayonini qadamma-qadam ko'rib chiqamiz:

1-qadam: Boshlang'ich cho'qqi sifatida 0-cho'qqini tanlaymiz:

1-qadam: Boshlang'ich cho'qqini tanlash
2-qadam: Tanlangan cho'qqidan chiquvchi qirralar orasidan eng kichigini tanlaymiz (0-1 qirrasi, vazni 9):

2-qadam: Minimal vaznli qirrani qo'shish (0-1: 9)
3-qadam: Endi {0, 1} cho'qqilaridan tashqariga chiquvchi qirralar orasidan eng kichigini tanlaymiz (1-3 qirrasi, vazni 19):

3-qadam: Navbatdagi minimal qirrani qo'shish (1-3: 19)
4-qadam: {0, 1, 3} cho'qqilaridan yangi cho'qqilarga olib boruvchi eng kichik qirrani tanlaymiz (3-4 qirrasi, vazni 31):

4-qadam: Minimal qirrani qo'shish (3-4: 31)
5-qadam: {0, 1, 3, 4} cho'qqilaridan hali kirmagan 2-cho'qqiga olib boruvchi eng kichik qirrani tanlaymiz (3-2 qirrasi, vazni 51):

5-qadam: Minimal qirrani qo'shish (3-2: 51)
6-qadam: Barcha 5 ta cho'qqi qamrab olindi va qamrovchi daraxt to'liq shakllantirildi:

6-qadam: Qamrovchi daraxt to'liq shakllandi (Minimum Spanning Tree)

Prim algoritmi psevdokodi

Prim algoritmining psevdokodi bizda ikkita cho'qqilar to'plami mavjudligini ko'rsatadi: U va V - U.

U to'plamiga allaqachon tashrif buyurilgan cho'qqilar kiradi.
V - U to'plamiga esa hali tashrif buyurilmagan cho'qqilar kiradi.

Biz birma-bir eng kichik vaznli qirra orqali V - U to'plamidan cho'qqilarni U to'plamiga o'tkazib boramiz.

text

T = ∅;
U = { 1 };
while (U ≠ V)
    let (u, v) be the lowest cost edge such that u ∈ U and v ∈ V - U;
    T = T ∪ {(u, v)}
    U = U ∪ {v}

Dasturiy kod

Grafni ifodalash uchun qo'shnilik matritsasi (Adjacency Matrix) qo'llanilgan, biroq samaradorlikni oshirish uchun ushbu algoritmni qo'shnilik ro'yxati (Adjacency List) va min-heap (ustuvorlik navbati) yordamida ham amalga oshirish mumkin.

package main

import (
	"fmt"
	"math"
)

func main() {
	INF := math.MaxInt32
	V := 5

	// Grafni qo'shnilik matritsasi (adjacency matrix) orqali ifodalash
	G := [][]int{
		{0, 9, 75, 0, 0},
		{9, 0, 95, 19, 42},
		{75, 95, 0, 51, 66},
		{0, 19, 51, 0, 31},
		{0, 42, 66, 31, 0},
	}

	selected := make([]bool, V)
	noEdge := 0

	// 0-cho'qqidan boshlaymiz va uni tanlangan deb belgilaymiz
	selected[0] = true

	fmt.Println("Edge : Weight\n")
	for noEdge < V-1 {
		minimum := INF
		x, y := 0, 0

		for i := 0; i < V; i++ {
			if selected[i] {
				for j := 0; j < V; j++ {
					if !selected[j] && G[i][j] != 0 {
						if minimum > G[i][j] {
							minimum = G[i][j]
							x = i
							y = j
						}
					}
				}
			}
		}

		fmt.Printf("%d-%d:%d\n", x, y, G[x][y])
		selected[y] = true
		noEdge++
	}
}

Prim va Kruskal algoritmlari taqqosi

Kruskal algoritmi ham minimal qamrovchi daraxtni topuvchi yana bir mashhur algoritm bo'lib, quyidagi farqlarga ega:

Kruskal algoritmi cho'qqidan emas, balki butun graf qirralaridan boshlaydi: qirralarni vaznlari bo'yicha saralab olib, sikl hosil qilmaydiganlarini birma-bir daraxtga qo'shib boradi.
Prim algoritmi esa bitta cho'qqidan boshlanib, har bir qadamda faqat joriy daraxtga tutash bo'lgan eng arzon qirra hisobiga daraxtni uzluksiz o'stirib boradi.

Prim algoritmining murakkabligi

Vaqt murakkabligi (Time Complexity):
- Qo'shnilik matritsasi (Adjacency Matrix) bilan: O(V^2).
- Qo'shnilik ro'yxati (Adjacency List) va ikkilik to'da (Binary Heap) bilan: O(E log V).
- Fibonachchi to'dasi (Fibonacci Heap) bilan: O(E + V log V).
Xotira murakkabligi (Space Complexity): O(V).

Prim algoritmining qo'llanilishi

Elektr tarmoqlari kabellarini yotqizish: Minimal xarajat bilan barcha iste'molchilarga elektr liniyalarini tortish.
Tarmoqlarni loyihalash: Aloqa va kompyuter tarmoqlarida uzellarni optimal bog'lash.
Tarmoq sikllarini oldini olish protokollari: Tarmoq kommutatorlarida aylanma sikllar (loop) yuzaga kelmasligi uchun Spanning Tree Protocol (STP) protokollarida foydalaniladi.

Oldingi

Keyingi