Universitetining jizzax filiali amaliy matematika fakulteti «kompyuter ilmlari va dasturlashtirish»

Tanlangan 
tugunlar 
to’plami 
(u,v) qirra 
V/Utanla
nmagan 
tugunlar 
to’plami 
Izoh 
{ }
{A,B,C,D,
E,F,G}
Boshlang’ich graf 
{D}
(D,A)=5 
V 
(D,B) = 9 
(D,E)= 
15 
(D,F) = 6
{A,B,C,E,
F,G}
D 
tugundan 
boshlaymiz 
A, B, E i F lar D bilan 
boqlangan. A tugun — D ga 
eng yaqin bo’lganligi uchun 
shu tugun olinadi.
{A,D}
(D,B) = 9 
(D,E)= 
15 
(D,F) = 6
(A,B) = 7 V
{B,C,E,F,
G}
D yoki A 
ga 
eng 
yaqin 
bo’lgan 
tugunni 
topamiz. B - D 9, A —D 
7. E gacha masofa 15, F —
gacha 6. F eng yaqin tugun.
{A,B,D,F}
(B,C) = 8 
(B,E)=7 
V
(D,B) = 9 sikl 
(D,E)= 
15 
(F,E) 
= 
8 
(F,G)= 11
{C,E,G}

---

6 
{A,B,D,E,F
}
(B,C) = 8 
(D,B) = 9 sikl 
(D,E) = 15 
sikl 
(E,C) = 5 V 
(E,G) = 9 
(F,E) = 8 sikl 
(F,G) = 11
{C,G}
{A,B,C,D,E
,F}
(B,C) = 8 sikl 
(D,B) = 9 sikl 
(D,E) = 15 
sikl 
(E,G) = 9 V 
(F,E) = 8 sikl 
(F,G) = 11
{G}
{A,B,C,D,E
,F,G}
(B,C) = 8 sikl 
(D,B) = 9 sikl 
(D,E) = 15 
sikl 
(F,E) = 8 sikl 
(F,G) = 11 
sikl
{ }
Minimal 
narxli 
daraxtlar 
skleti qurildi. Bunda og’irligi 
39 bo’ldi.
Yuqoridagi graf uchun qoʻshnilik matrisasi 
A B C D E F G 
0 7 0 5 0 0 0
7 0 8 9 7 0 0 
0 8 0 0 5 0 0 
5 9 0 0 15 6 0 
0 7 5 15 0 8 9 
0 0 0 6 8 0 11 
0 0 0 0 9 11 0

---

7 
Prima algoritmi quyidagi tartibda ishlaydi: 
 
Dastlabki berilgan graf 
 
1-bosqich. Uchni tanlash
 
 
 
2-bosqich. Ushbu uchdan eng qisqa qirrani tanlash va uni qo‘shish 
 
 
 
3-bosqich. Grafdan hali tanlanmagan eng yaqin uchni tanlash 
 
 
 
4-bosqich. Grafda hali topilmagan eng yaqin uchni tanlang, agar bir 
nechta variant, tasodifiy birini tanlash 

---

8 
 
2-rasm.Keyingi bosqichlar. Yuqoridagi ishlarni daraxt hosil boʻlguncha 
takrorlash 
Dastur Kodi: 
using
System; 
using
System.Collections.Generic; 
using
System.ComponentModel; 
using
System.Data; 
using
System.Drawing; 
using
System.Linq; 
using
System.Text; 
using
System.Windows.Forms; 
namespace
Prim_algoritmi 
{ 
public
partial
class
Form1
: Form 
{ 
public
Form1
() 
{ 
InitializeComponent(); 
} 
private
void
button1_Click(
object
sender, EventArgs e) 
{ 
if
(textBox1.Text != 
""
&& textBox2.Text != 
""
) 
{ 
int
n = 
int
.Parse(textBox1.Text); 
int
[,] cost = 
new
int
[n, n]; 
// Qushnilik matritsasini tashkil etish
string
[] matrixElements = textBox2.Text.Split(
' '
); 
if
(matrixElements.Length != n * n) 
{ 
MessageBox.Show(
"Qo'shnilik matritsasi elementlari noto'g'ri 
kiritildi.Iltimos qaytadan urunib ko'ring..."
, 
"Xatolik"
); 
return
; 
} 
int
index = 0; 
for
(
int
i = 0; i < n; i++) 
{ 
for
(
int
j = 0; j < n; j++) 
{ 
cost[i, j] = 
int
.Parse(matrixElements[index]); 
index++; 
} 

---

9 
} 
int
[] visited = 
new
int
[n]; 
int
min, mincost = 0; 
int
[] path = 
new
int
[n - 1]; 
int
path_index = 0; 
visited[0] = 1; 
// Minimum keshlash algoritmi
while
(path_index < n - 1) 
{ 
min = 
int
.MaxValue; 
int
a = -1, b = -1; 
for
(
int
i = 0; i < n; i++) 
{ 
if
(visited[i] == 1) 
{ 
for
(
int
j = 0; j < n; j++) 
{ 
if
(visited[j] == 0 && cost[i, j] != 0 && cost[i, 
j] < min) 
{ 
min = cost[i, j]; 
a = i; 
b = j; 
} 
} 
} 
} 
if
(a != -1 && b != -1) 
{ 
visited[b] = 1; 
path[path_index] = b; 
path_index++; 
mincost += min; 
} 
cost[a, b] = cost[b, a] = 
int
.MaxValue; 
} 
// Yakuniy yechimni joylash
richTextBox1.Text = 
"Minimal yo'l: "
; 
richTextBox1.Text += 
"1 --> "
; 
for
(
int
i = 0; i < n - 1; i++) 
{ 
richTextBox1.Text += (path[i] + 1).ToString(); 
if
(i < n - 2) 
{ 
richTextBox1.Text += 
" --> "
; 
} 
} 
richTextBox1.Text += 
"\nMinimal narx: "
+ mincost.ToString(); 
} 
else
{ 
MessageBox.Show(
"To'ldirilmagan maydonlar mavjud!!!"
, 
"Xatolik"
); 
} 
} 
private
void
button2_Click(
object
sender, EventArgs e) 
{ 

---

10 
if
(textBox1.Text != 
""
|| textBox2.Text!=
""
||richTextBox1.Text!=
""
) 
{ 
textBox1.Text = textBox2.Text = richTextBox1.Text = 
""
; 
} 
} 
} 
} 
Dasturning vizual ko‘rinishi: 
Algoritmni baholash
, Yomon holatda -
. 
Kraskal algoritmi. 
Ushbu algoritm 1956 yili Kraskal tomonidan ishlab chikilgan. 
Faraz qilamiz, V = {1, 2, .... n} boʻgʻimlar toʻplamidan iborat va Ye qirralar 
toʻplamida aniqlangan s narx funksiyasi bilan berilgan G=(V, Ye) bogʻlangan graf 
boʻlsin. Kruskal algoritmida G graf uchun minimal narxli daraxtlar skletini qurish G 
grafning faqat n ta boʻgʻimlaridan tashkil topgan va qirralari boʻlmagan T=(V, ø) 
grafdan boshlanadi. Shunday qilib, har bir boʻgʻim bogʻlangan (oʻzi-oʻzi bilan) 
komponent hisoblanadi. Algoritm bajarilishi vaqtida bogʻlangan komponentlar 
naboriga ega boʻlamiz, asta-sekin birlashtirib daraxtlar skletini tashkillashtiramiz.  
Asta-sekin oʻsuvchi bogʻlangan komponentlarni qurishda Ye toʻplamdan 
qirralar ularning narxi oʻsishi tartibida navbatma-navbat tekshiriladi. Agar 
navbatdagi qirra turli komponentlardagi ikkita boʻgʻimni birlashtirsa, u holda bu 
qirra T grafga qoʻshiladi. Agar bu qirra bitta komponentning ikkita boʻgʻimini 

---

11 
birlashtirsa, u tashlab yuboriladi, chunki uning bogʻlangan komponentga qoʻshilishi 
sikl hosil boʻlishiga olib keladi. G grafning barcha boʻgʻimlari bitta komponentga 
tegishli boʻlsa, T minimal narxli daraxtlar skletini qurish bu graf uchun tugaydi. 
Kruskal algoritmini amalga oshirish bosqichlari quyidagicha: 
1) Barcha qirralarni quyidan yuqorigacha saralash.
2) Vazni eng kichik qirrasini oling va uni daraxtga qo'shing. Agar qirra 
qoʻshilganda, sikl hosil boʻlsa, u holda bu qirrani olib tashlang.
3) Barcha uchlarga yetguncha qirralarni qo'shishni davom eting. Quyidagi 
rasmda minimal uzunlikka kiritilgan qirralar qizil rang bilan, qora rang bilan esa 
nomzodlar ulardan eng kam darajadagi qirra tanlangan. 

---

12 
3-rasm.Kruskal algoritmining bajarilish ketma-ketligi. 
Misol 
S bogʻlangan komponentlar toʻplami kerak, bu uchun quyidagi operatorlar 
ishlatiladi: 
1. MERGE(A, V, S) operatori S nabordan A va V bogʻlangan komponentlarni 
birlashtiradi va natijani A yoki V ga joylashtiradi. 
2. FIND(v, S) funksiyasi S nabordan v boʻgʻimni oʻz ichiga olgan 
komponentning nomini qaytaradi. 

---

13 
3. INITIAL(A, v, S) operatori naborda faqat v boʻgʻimdan iborat A nomli 
komponentni yaratadi. 
Ushbu algoritm 
O (M log N + N
2
)
vaqtda bajariladi. Qirralarni saralash 
uchun O(M logN) ta operasiya kerak buladi. Tugun u yoki bu qism daraxtga tegishli 
boʻlsa, 
tree_id massiv yordamida saqlanadi, bu massivda har bir tugun uchun u 
tegishli boʻlgan daraxt nomeri saqlanadi. Har bir qirra uchun O(1) vaqtda uning 
tugunlari turli daraxtlarga tegishli ekanligini aniqlanadi. Nihoyat, ikkita daraxtni 
birlashtirish O (N) vaqtda bajariladi. Birlashtirish operatori O(N) oʻtishda 
bajarilishini hisobga olsak, O (M log N + N
2
)
kelib chikadi. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

---

14 
Xulosa 
Prim algoritmi, grafda minimum yuk masofalari yig'indisini topishda 
foydalaniladigan algoritm hisoblanadi. Bu algoritm, grafda eng kam yuk masofaga 
ega bo'lgan tugunni tanlash orqali ishga tushiriladi va undan keyin tanlangan 
tugunga bog'liq barcha qolgan tugunlarni jadvallash va ularning yuklarini hisoblash 
jarayonidan iborat.Prim algoritmi, barcha grafni aylanib, barcha tugunlarni 
tekshirishdan ozod qiladi va eng kam yukli tugunni tanlash orqali yuqori darajali 
yuklarni qo'shish orqali yana tekshirishni takrorlaydi. Algoritmda qo'shilgan 
tugunlar o'rtasidagi yuk masofalari yig'indisi, minimal yuklar yig'indisi hisoblanadi. 
Foydalanilgan adabiyotlar: 
1. Horstmann, Cay S. C++ for everyone/Cay S. Horstmann. Printed in the United 
States of America - 2nd ed. 2010. – P. 562.
2. Horton I.-Beginning Visual C++ 2012/ I.Horton. Published simultaneously in 
Canada.–2012. –P. 988. 
3. Nazirov Sh.A., Qobulov R.V., Bobojanov M.R., Raxmanov Q.S. S va C++ 
tili. “Voris- nashriyot” MChJ, Toshkent 2013, 488 b. 
Elektron resurslar: 
1. 
https://hozir.org/
 
2.
https://rextester.com/MBGGS38908