|
O‘zbekiston respublikasi axborot texnologiyalari vа kommunikatsiyalarini rivojlantirish vazirligi
|
| bet | 2/3 | | Sana | 21.02.2023 | | Hajmi | 0.68 Mb. | | #43065 |
Bog'liq AL Mustaqil ish Botir Tulyaganov 44-20Kruskal Algoritmi
Kruskal algoritmi uning g'oyasi va amalga oshirilishida juda oddiy. Bu barcha qirralarni uzunlikni oshirish tartibida saralashdan va agar ular turli xil ulanish komponentlarini birlashtirsa, ularni navbat bilan minimal skeletga qo'shishdan iborat.
Rasmiyroq: minimal skeletga kiritilgan ba'zi qovurg'alarni allaqachon topaylik. Turli xil ulanish komponentlarini bog'laydigan barcha qovurg'alar orasida minimal uzunlikdagi qovurg'a minimal skeletga kiritilishi aytiladi.
Kruskal algoritmini amalga oshirish uchun siz qirralarni uzunlik o'sishi bo'yicha saralashingiz kerak (buning uchun biz o'z ma'lumot turimizdan foydalanamiz) va chekka ulanishning ikki xil komponentini birlashtirganligini tekshirishingiz kerak. Buning uchun biz DSU ma'lumotlar strukturasi yordamida joriy ulanish komponentlarini saqlab qolamiz.
Kruskal algoritmining ishlashini vizualizatsiya qilish:
Kruskal algoritmini c++ da amalga oshirish
Biz tegishli ma'ruzadan barcha optimallashtirishlar bilan DSU dasturidan foydalanamiz:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include
|
|
| |
