MODELS AND METHODS IN MODERN SCIENCE
International scientific-online conference
74
PRIM ALGORITMINING ASOSIY TAMOYILLARI VA MINIMAL
ULANISH DARAXTI
Sh.R.Farmonov
Farg’ona davlat universiteti amaliy matematika va
informatika kafedrasi katta oʻqituvchisi
farmonovsh@gmail.com
Ch.M.Sohibova
Farg’ona davlat universiteti 2-kurs talabasi
https://doi.org/10.5281/zenodo.14498685
Annotatsiya.
Ushbu maqolada prim algoritmi mavzusi keng tahlil qilingan.
Asosan, prim algoritmi nima maqsadlarda qo’llanilishi, uning asosiy
tushunchalari ishlash mexanizmi, algoritmning ishlash tartibi yoritilgan. Shu
bilan birga prim algoritmining ishlashiga doir misollar keltirilib, C# dasturlash
tilida ko’rib chiqilgan.
Kalit so`zlar:
minimal bog’lanish daraxti(MST), graf, tugun, qirra,
boshlang’ich tugun, qo’shiluvchi qirra, ishonchlilik , samaradorlik.
Annotation
. In this article, the topic of prime algorithm is extensively
analyzed. Basically, what is the purpose of the prim algorithm, its main concepts,
the mechanism of operation, the procedure of the algorithm are explained. At
the same time, examples of the operation of the prim algorithm are given and
reviewed in the C# programming language.
Key words:
minimum spanning tree (MST), algorithm, graph, node edge,
starting node, joining edge, reliability, efficiency.
Аннотация.
В данной статье подробно анализируется тема простого
алгоритма. В основном объясняется назначение алгоритма Прим, его
основные понятия, механизм работы, порядок работы алгоритма. Прим
этом приводятся и рассматриваются примеры работы алгоритма прим на
языке программирования C#.
Ключевые слова
: минимальное остовное дерево (MST), алгоритм,
граф, ребро узла, начальный узел, соединяющее ребро, надежность,
эффективность.
Algoritm juda ham ko’p yondashuvlarni talab qilmoqda. Prim algoritmi- bu
graf nazariyasida minimal bog'lanish daraxtini (MST) topish uchun
ishlatiladigan samarali algoritm. Minimal bog’lanish daraxti – bu berilgan
grafning barcha tugunlarini birlashtiruvchi va eng kichik og'irlikka ega bo`lgan
daraxtdir. Prim algoritmi ko’plab amaliy sohalarda, masalan, tarmoq dizayni va
transport muammolarini hal qilishda keng qo’llaniladi. Ushbu maqolada prim
MODELS AND METHODS IN MODERN SCIENCE
International scientific-online conference
75
algoritmi to’g’risidagi asosiy bilimlar, ularning ishlash mexanizmlari va o’zaro
aloqasi haqida tahliliy fikrlar olib boriladi.
Prim algoritmining asosiy tushunchalari
Prim algoritmi, 1930-yillarda Vaclav Prim tomonidan taklif qilingan bo’lib,
u og’irlikli grafdan MST ni topish uchun ishlatiladi. Algoritmning asosiy maqsadi,
grafdagi barcha tugunlarni bog’laydigan va umumiy og’irligi minimal bo’lgan
qirralar to’plamini aniqlashdir.
Prim algoritmining tuzilishi va ishlashi
Graf nazariyasi kompyuter fanlari va matematikada muhim o’rin tutadi.
Ayniqsa, minimal bog'lanish daraxtlarini (MST) topish masalasi ko’plab amaliy
muammolarni hal qilishda qo’llaniladi. Ushbu maqolada, Prim algoritmi haqida
batafsil ma’lumot beramiz. Prim algoritmi - bu grafda minimal bog’lanish
daraxtini topish uchun ishlatiladigan samarali usuldir.
Graf nazariyasi
Graf - bu tugunlar (noktalar) va ularni bog’laydigan qirralardan iborat
tuzilma. Har bir qirrada og’irlik (masofa yoki xarajat) bo’lishi mumkin. Minimal
bog’lanish daraxti - bu grafning barcha tugunlarini birlashtiruvchi eng kichik
og’irlikka ega bo’lgan bog’lanish daraxtidir.
Prim algoritmi quyidagi bosqichlarni o’z ichiga oladi:
• Boshlanish: Tasodifiy bir tugun tanlanadi va dastlabki MST boshlanadi.
• Qirralarni tanlash: MST ga qo’shilishi mumkin bo’lgan eng kichik og’irlikka
ega qirra tanlanadi.
• Yangilanish: Tanlangan qirra MST ga qo’shiladi va yangi qirralar MST ga
kiritiladi.
• Takrorlash: Ushbu jarayon barcha tugunlar MST ga kiritilgunga qadar
davom etadi.
Prim algoritmining ishlash tartibi:
1. Dastlabki tugunni tanlang va uni MST ga qo’shing.
2. MST ga qo’shilmagan tugunlardan eng kichik og’irlikka ega qirra orqali
yangi tugunni tanlang.
• Dastlabki tugun sifatida A ni tanlaymiz.
• A dan B ga eng kichik og’irlik (1) bilan o’tamiz.
• B dan C ga (1) va keyin C dan D ga (2) o’tamiz.
Natijada quyidagicha hosil bo’lgan: MST: A-B-C-D.
Murakkablik
Prim algoritmining vaqt murakkabligi O(E log V) ga teng, bu yerda E - qirralar
soni, V - tugunlar soni. Bu murakkablik grafning hajmiga qarab samaradorligini
MODELS AND METHODS IN MODERN SCIENCE
International scientific-online conference
76
ta’minlaydi.
Prim algoritmi minimal bog’lanish daraxtini topish uchun samarali usuldir. U
tarmoq dizayni, transport va boshqa sohalarda keng qo'llaniladi. Ushbu
maqolada Prim algoritmining asosiy tushunchalari va ishlash mexanizmi ko’rib
chiqiladi, bu esa o’z navbatida grafik ma’lumotlar strukturalarini o’rganishda
muhim ahamiyatga ega. Prim algoritmi - graf nazariyasi sohasida ishlatiladigan
algoritm bo’lib, u bog’langan, og’irlikli va yo’qotishsiz grafda minimal bog’lanish
daraxtini (MST) topish uchun qo’llaniladi. Prim algoritmi, shuningdek, "yashil"
yoki "kengaytiriladigan" algoritm sifatida ham tanilgan, chunki u dastlabki bir
nuqtadan boshlanib, yangi tugunlar qo’shib boradi.
Prim algoritmi
ko’plab amaliyotlarda qo’llaniladi
1.
Tarmoq dizynida
-
telefon, internet yoki elektr tarmoqlarining minimal
xarajat bilan qurilishi uchun.
2.
Transport va logistikada – yuklarni tashish uchun eng samarali yo’llarni
aniqlashda.
3.
Maqsadli tarmoqlar – kompyuter tarmoqlarida ma’lumotlarni uzatish
uchun eng optimal yo’llarni topishda,
# Shuningdek,
Prim algoritmining afzalliklari
va kamchiliklari
haqida
ham aytib o’tmoqchiman.
Afzalliklari:
oddiy va tushunarli, kichik graflar uchun samarali.
Kamchiliklari:
kata graflar uchun vaqt va xotira sarfi yuqori bo’lishi, agar
graf kata bo’lsa, boshqa algoritmlar ( masalan, Kruskal algoritmi ) samaraliroq
bo’lishi.
Prim algoritmining ishlashiga doir masala:
Faraz qilaylik, bizda 4 ta shahar mavjud va ular o'rtasidagi yo'llar xarajatlari
berilgan. Biz minimal xarajat bilan barcha shaharlarni bog'laydigan yo'lni
topishimiz kerak.
Prim algoritmining ishlashiga doir masala:
Faraz qilaylik, bizda 4 ta shahar mavjud va ular o'rtasidagi yo'llar xarajatlari
berilgan. Biz minimal xarajat bilan barcha shaharlarni bog'laydigan yo'lni
topishimiz kerak.
C# Dasturlash tilida yechim:
using
System;
namespace
ConsoleApp1
{
internal
class
Program
MODELS AND METHODS IN MODERN SCIENCE
International scientific-online conference
77
{
const
int
V = 4;
// Shaharlar soni
// Minimal bog'lanish daraxtini qurish uchun Prim algoritmi
static
void
Prim(
int
[,] graph)
{
int
[] parent =
new
int
[V];
// Natijaviy daraxt
int
[] key =
new
int
[V];
// Minimal xarajatlar
bool
[] mstSet =
new
bool
[V];
// MST to'plami
// Barcha kalitlarni cheksizga o'rnatamiz
for
(
int
i = 0; i < V; i++)
{
key[i] =
int
.MaxValue;
mstSet[i] =
false
;
}
// Birinchi shaharni tanlaymiz
key[0] = 0;
// Birinchi shahar
parent[0] = -1;
// Birinchi shaharning ota-onasi yo'q
for
(
int
count = 0; count < V - 1; count++)
{
// Minimal kalitni tanlang
int
u = MinKey(key, mstSet);
// Tanlangan shaharni MST ga qo'shamiz
mstSet[u] =
true
;
// Qo'shni shaharlar uchun kalitlarni yangilang
for
(
int
v = 0; v < V; v++)
{
// Agar v shahriga yo'l mavjud bo'lsa va u MST ga kirmasa
// va yangi kalit kichik bo'lsa
if
(graph[u, v] != 0 && !mstSet[v] && graph[u, v] < key[v])
{
parent[v] = u;
key[v] = graph[u, v];
MODELS AND METHODS IN MODERN SCIENCE
International scientific-online conference
78
}
}
}
// Natijani chiqaramiz
PrintMST(parent, graph);
}
// Minimal kalitni topish funksiyasi
static
int
MinKey(
int
[] key,
bool
[] mstSet)
{
int
min =
int
.MaxValue, minIndex = -1;
for
(
int
v = 0; v < V; v++)
{
if
(!mstSet[v] && key[v] < min)
{
min = key[v];
minIndex = v;
}
}
return
minIndex;
}
// MST ni chiqarish funksiyasi
static
void
PrintMST(
int
[] parent,
int
[,] graph)
{
Console.WriteLine(
"Shaharlar
o'rtasidagi
minimal
bog'lanish
daraxti:"
);
for
(
int
i = 1; i < V; i++)
{
Console.WriteLine(
$"Shahar
{parent[i]}
- Shahar
{i}
, Xarajat:
{graph[i, parent[i]]}
"
);
}
}
static
void
Main(
string
[] args)
{
MODELS AND METHODS IN MODERN SCIENCE
International scientific-online conference
79
// Shaharlar o'rtasidagi xarajatlar grafi
int
[,] graph =
new
int
[,]
{
{ 0, 2, 0, 6 },
{ 2, 0, 3, 8 },
{ 0, 3, 0, 0 },
{ 6, 8, 0, 0 }
};
Prim(graph);
Console.ReadKey();
}
}
Natija quyidagicha :
Shaharlar o'rtasidagi minimal bog'lanish daraxti:
Shahar 0 - Shahar 1, Xarajat: 2
Shahar 1 - Shahar 2, Xarajat: 3
Shahar 0 - Shahar 3, Xarajat: 6
Ushbu dastur ishga tushirilganda shaharlar o'rtasidagi minimal bog'lanish
daraxti va xarajatlarini chiqaradi. Bu transport sohasida xarajatlarni
minimallashtirish uchun foydalanilishi mumkin.
Kodning tushuntirilishi:
• V - shaharlar soni.
• Prim funksiyasi minimal bog'lanish daraxtini quradi.
• MinKey funksiyasi eng kichik kalitni topadi.
• PrintMST funksiyasi natijaviy bog'lanish daraxtini chiqaradi.
• Main funksiyasida shaharlar o'rtasidagi xarajatlar grafi berilgan va Prim
funksiyasi chaqiriladi.
Yuqoridagi masalaga izoh sifatida ma’lumot bermoqchiman:
1. Grafni ifodalash: Graf matritsa ko'rinishida berilgan. Har bir element
graph [i, j] i va j tugunlari orasidagi og'irlikni ifodalaydi. Agar element 0 bo'lsa,
demak u tugunlar orasida bog'lanish yo'q.
2. MinKey funksiyasi: Bu funksiya eng kichik kalitga ega tugunni topadi.
3. PrimMST funksiyasi: Bu funksiya Prim algoritmini bajaradi va MST ni
hosil qiladi.
MODELS AND METHODS IN MODERN SCIENCE
International scientific-online conference
80
4. PrintMST funksiyasi: Bu funksiya MST ni chiqaradi.
5. Main funksiyasi: Dastur boshlanishi va grafni belgilash joyi.
Prim algoritmi-bu minimal bog`lanish daraxtini topish uchun samarali va
intuitiv yechimdir. Har bir qadamda eng kichik og`irlikdagi qirrani tanlab, MST
ni quradi.Uning oddiyligi va ko`p hollarda qo`llanilishi, keng doirasi uni ko`plab
amaliy muammolarni hal qilishda juda qimmatli qiladi, shuningdek,kompyuter
fanlari va muhandislik sohalarida juda foydalidir.Kelajakda prim algoritmi
telekommunikatsiya va computer tarmoqlarini loyihalashada, energiya yoki suv
ta’minoti tizimlarida resurslarni samarali taqsimlash uchun, 3D modellarni
yaratishda yoki tasvirlarni siqishda, kata ma’lumotlar to’plamlaridagi
bog’lanishlarni
o’rganishda,
klasterlashda,
ijtimoiy
tarmoqlardagi
bog’lanishlarni tahlil qilishda foydalaniladi
Foydalanilgan adabiyotlar:
1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2009). “Introduction to
Algorithms”.
2. Kleinberg, J., Tardos, É. (2005). “Algorithm Design”.
3. Garey, M. R., Johnson, D. S. (1979). “Computers and Intractability: A Guide to
the Theory of NP-Completeness”. W.H. Freeman and Company.
4.”A Minimum Spanning Tree Algorithm” by C. Prim (1957). An Efficient.
5.”Algorithm for Finding Minimum Spanning Trees” by J. Kleinberg and Eva
Tardos.
6. Sedgewick, R., Wayne, K. (2011). “Algorithms” (4th ed.). Addison-Wesley.
7. Tarjan, R. E. (1983). "Data Structures and Network Algorithms." SIAM.
8. Boros, E., Hammer, P. L. (1991). "Theoretical and Practical Aspects of Graph
Theory."Graph Theory and Applications”.
9. Prim, C. (1957). "Shortest Connection Networks and Some Generalizations."
“Bell System Technical Journal”.
10. West, D. B. (2001). *Introduction to Graph Theory*. Prentice Hall.
11. Raxmonjonovich, F. S., & Saidahmad o’g’li, I. S. (2024). BFS ALGORITMI VA
UNING XAVFSIZLIK SOHASIDAGI ROLI. SCIENTIFIC APPROACH TO THE
MODERN EDUCATION SYSTEM, 3(31), 117-123.
12. Raxmonjonovich, F. S. (2024). SUN’IY INTELEKT VA MASHINANI
O’QITISHDA MATEMATIK ALGORITMDAN FOYDALANISH. Modern education
and development, 15(5), 107-116.
13. Raxmonjonovich, F. S. (2024). GRAF NAZARIYASIDA MINIMAL BOG’LANISH
DARAXTINI TOPISHDA PRIM ALGORITMINING QO’LLANILISHI. Modern
education and development, 15(5), 329-337.
MODELS AND METHODS IN MODERN SCIENCE
International scientific-online conference
81
14. Raxmonjonovich, F. S. (2024). MA'LUMOTLARNI SIQISHDA BITLI
ALGORITMLARDAN FOYDALANISH. Modern education and development, 15(5),
320-328.
15. Raxmonjonovich, F. S. (2024). AXBOROTLARNI SHIFRLASHDA MATEMATIK
ALGORITMLARDAN FOYDALANISH. Modern education and development, 15(5),
338-344.
16. Farmonov, S. R. (2024). BFS ALGORITIMI ORQALI TOPOLOGIK TARTIBNI
ANIQLASH. ОБРАЗОВАНИЕ И НАУКА В XXI ВЕКЕ, (56-5).
