62 / 69

Kruskal's Algorithm

Kruskal algoritmi nima?

Kruskal algoritmi — bu berilgan bog'langan va vaznli graf uchun minimal qamrovchi daraxtni (Minimum Spanning Tree - MST) topuvchi mashhur algoritmdir.

U grafning barcha qirralari orasidan quyidagi talablarga javob beradigan qirralar qism-to'plamini aniqlaydi:

Grafning har bir cho'qqisini qamrab oluvchi daraxt (sikl hosil qilmaydigan tuzilma) hosil qiladi;
Grafdan hosil qilinishi mumkin bo'lgan barcha qamrovchi daraxtlar orasida qirralar vaznlari yig'indisi eng minimal bo'ladi.

Kruskal algoritmi qanday ishlaydi?

Kruskal algoritmi ham greedy (ochko'z) algoritmlar toifasiga kiradi. Ya'ni, u global optimal natijaga erishish umidida har bir qadamda lokal optimal variantni tanlaydi.

Algoritm eng kam vaznga ega bo'lgan qirralardan boshlaydi va maqsadga erishguncha (barcha cho'qqilar bog'languncha) qirralarni qo'shishda davom etadi.

Kruskal algoritmini amalga oshirish bosqichlari quyidagicha:

Grafning barcha qirralarini vaznlari bo'yicha kichigidan kattasiga (o'sish tartibida) saralash.
Eng kichik vaznli qirrani olib, qamrovchi daraxtga qo'shish. Agar ushbu qirrani qo'shish natijasida sikl (yopiq halqa) hosil bo'lsa, ushbu qirra rad etiladi.
Daraxt barcha cho'qqilarni qamrab olguncha (ya'ni V - 1 ta qirra to'planguncha) qirralarni qo'shishda davom etish.

Kruskal algoritmi misoli

Keling, quyidagi vaznli graf misolida algoritmni ko'rib chiqamiz:

Vaznli graf berilgan:

Vaznli graf bilan boshlaymiz
Eng kichik vaznli qirrani tanlaymiz (agar bir nechta bo'lsa, istalgan birini tanlash mumkin):

Eng kam vaznli qirrani tanlash
Navbatdagi eng qisqa qirrani tanlab, daraxtga qo'shamiz:

Keyingi eng qisqa qirrani tanlash va qo'shish
Sikl hosil qilmaydigan keyingi eng qisqa qirrani tanlaymiz:

Sikl hosil qilmaydigan keyingi qirrani tanlash va qo'shish
Jarayonni davom ettiramiz, bunda sikl hosil qiluvchi har qanday qirra tashlab ketiladi:

Siklsiz keyingi qirra qo'shiladi
Qamrovchi daraxt to'liq hosil bo'lgunga qadar (V - 1 ta qirra qo'shilguncha) jarayon takrorlanadi:

Qamrovchi daraxt to'liq hosil bo'lguncha takrorlash

Kruskal algoritmi psevdokodi

Har qanday minimal qamrovchi daraxt algoritmi yangi qirrani qo'shish sikl hosil qilishi yoki qilmasligini tekshirishga asoslanadi.

Buni eng samarali tekshirish usuli — Union-Find (Disjoint Set Union - DSU) algoritmidir. Union-Find algoritmi cho'qqilarni alohida to'plamlarga (klasterlarga) ajratadi va ikki cho'qqi ayni bir to'plamga tegishli ekanligini tezkor tekshirish imkonini beradi. Agar ikki cho'qqi allaqachon bitta to'plamda bo'lsa, ularni tutashtiruvchi qirrani qo'shish sikl hosil qiladi va u rad etiladi.

text

KRUSKAL(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

Dasturiy kod

package main

import (
	"fmt"
	"sort"
)

type Edge struct {
	u, v, w int
}

type Graph struct {
	V     int
	edges []Edge
}

func (g *Graph) AddEdge(u, v, w int) {
	g.edges = append(g.edges, Edge{u, v, w})
}

// Find funksiyasi (Disjoint Set)
func find(parent []int, i int) int {
	if parent[i] == i {
		return i
	}
	parent[i] = find(parent, parent[i])
	return parent[i]
}

// Ikki to'plamni birlashtirish (Union by rank)
func applyUnion(parent, rank []int, x, y int) {
	xroot := find(parent, x)
	yroot := find(parent, y)
	if rank[xroot] < rank[yroot] {
		parent[xroot] = yroot
	} else if rank[xroot] > rank[yroot] {
		parent[yroot] = xroot
	} else {
		parent[yroot] = xroot
		rank[xroot]++
	}
}

// Kruskal algoritmini qo'llash
func (g *Graph) KruskalAlgo() {
	result := []Edge{}

	// 1-qadam: Qirralarni vaznlari bo'yicha o'sish tartibida saralash
	sort.Slice(g.edges, func(i, j int) bool {
		return g.edges[i].w < g.edges[j].w
	})

	parent := make([]int, g.V)
	rank := make([]int, g.V)
	for i := 0; i < g.V; i++ {
		parent[i] = i
	}

	i, e := 0, 0
	// V - 1 ta qirra tanlanguniga qadar davom etish
	for e < g.V-1 && i < len(g.edges) {
		edge := g.edges[i]
		i++
		x := find(parent, edge.u)
		y := find(parent, edge.v)

		// Agar sikl hosil bo'lmasa, qirrani daraxtga qo'shamiz
		if x != y {
			e++
			result = append(result, edge)
			applyUnion(parent, rank, x, y)
		}
	}

	for _, edge := range result {
		fmt.Printf("%d - %d: %d\n", edge.u, edge.v, edge.w)
	}
}

func main() {
	g := Graph{V: 6}
	g.AddEdge(0, 1, 4)
	g.AddEdge(0, 2, 4)
	g.AddEdge(1, 2, 2)
	g.AddEdge(1, 0, 4)
	g.AddEdge(2, 0, 4)
	g.AddEdge(2, 1, 2)
	g.AddEdge(2, 3, 3)
	g.AddEdge(2, 5, 2)
	g.AddEdge(2, 4, 4)
	g.AddEdge(3, 2, 3)
	g.AddEdge(3, 4, 3)
	g.AddEdge(4, 2, 4)
	g.AddEdge(4, 3, 3)
	g.AddEdge(5, 2, 2)
	g.AddEdge(5, 4, 3)

	g.KruskalAlgo()
}

Kruskal va Prim algoritmlari taqqosi

Prim algoritmi ham minimal qamrovchi daraxtni (MST) topuvchi mashhur algoritm bo'lib, lekin u boshqacha mantiq asosida ishlaydi:

Kruskal algoritmi qirralardan boshlaydi: barcha qirralarni vaznlari bo'yicha saralaydi va sikl hosil qilmaydigan eng kichik qirralarni global tanlab boradi.
Prim algoritmi esa cho'qqidan boshlaydi: bitta boshlang'ich cho'qqini tanlab, unga tutashgan va hali daraxtga kirmagan eng kichik vaznli qirralarni bosqichma-bosqich qo'shish orqali daraxtni kengaytirib boradi.

Kruskal algoritmining murakkabligi

Vaqt murakkabligi (Time Complexity): O(E log E) yoki O(E log V). Bu yerda E — qirralar soni, V — cho'qqilar soni. Qirralarni saralash O(E log E) vaqt oladi, Union-Find operatsiyalari esa deyarli doimiy O(E alpha(V)) vaqt oladi.
Xotira murakkabligi (Space Complexity): O(V + E).

Kruskal algoritmining qo'llanilishi

Elektr tarmoqlari va simlarini yotqizish: Shaharlar yoki binolar orasida minimal sim uzunligi sarflab to'liq elektr tarmog'ini yaratish.
Kompyuter tarmoqlari (LAN ulanishlari): Tarmoq kabellarining umumiy narxini minimallashtirgan holda barcha kompyuterlarni o'zaro bog'lash.

Oldingi

Keyingi