1. Algoritmning maqsadi va tushunchasi haqida tushuntirish Deykstra algoritmi qanday ishlaydi?

Prim algoritmi qanday ishlaydi? Prim algoritmining g'oyasi oddiy, 
kengaytirilgan daraxt barcha uchlari bir-biriga ulangan bo'lishi kerak. Shunday 
qilib, uchburchak  daraxtiqilish uchun vertikal qismlarning ikkita ajratilgan pastki 
qismlari (yuqorida muhokama qilingan) ulanishi kerak . Va uni minimal  cho'zish 
daraxtiqilish uchun ular minimal vazn chegarasi bilan bog'langan bo'lishi kerak . 
Algoritm 
1) MST-ga kiritilgan vertikallarni hisobga oladigan mstSet to'plamini yarating. 
2) Kirish grafigidagi barcha uchlarga kalit qiymatini belgilang. INFINITE sifatida 
barcha muhim qadriyatlarni boshlang. Kalit qiymatini birinchi vertex uchun 0 deb 
belgilang, 
shunda 
u 
birinchi 
tanlanadi. 
3) mstSet-da 
barcha 
vertikal 
qismlar 
mavjud 
emas 
... a) tepalik nuqtasiga Pick U erda emas mstSet va minimal muhim ahamiyatga 
ega. 
…. b) mstSet-ga u qo'shing. 
…. c) u- ning barcha qo'shni uchlarining kalit qiymatini yangilang. Kalit 
qiymatlarini yangilash uchun barcha qo'shni vertikalar bo'ylab takrorlang. Har 
qo'shni uch uchun v chet vazn bo'lsa, UV kam avvalgi asosiy qiymati qaraganda V , 
og'irligi sifatida kalit qiymati yangilash UV 
 
 
Kalit qiymatlarni ishlatish g'oyasi kesilgan joydan minimal og'irlik 
chegarasini tanlashdir . Kalit qiymatlari faqat MST-ga kiritilmagan uchlari uchun 
ishlatiladi, bu uchlari uchun kalit qiymati ularni MST ichiga kiritilgan uchlari bilan 
bog'laydigan minimal og'irliklarni bildiradi. 
Quyidagi 
misol 
bilan 
tushunaylik. 
 
O'rnatilgan mstSet dastlab bo'sh va vertikallarga berilgan kalitlar {0, INF, 
INF, INF, INF, INF, INF, INF}, bu erda INF cheksizdir. Endi minimal kalit 
qiymatiga 
ega 
vertexni 
tanlang. Vertex 
0 
tanlangan, 
uni mstSet-ga 
qo'shing . Shunday 
qilib, mstSet {0} 
bo'ladi. MstSet- ga qo'shgandan so'ng , 
qo'shni vertikallarning kalitlarini yangilang. 0 ga ulashgan vertikallar 1 va 7 dir. 1 

---

va 7 ning asosiy qiymatlari 4 va 8 kabi yangilanadi. Quyidagi subgrafda vertikal 
chiziqlar va ularning asosiy qiymatlari ko'rsatilgan, faqat cheklangan kalit 
qiymatlari bo'lgan uchlari ko'rsatilgan. MST-ga kiritilgan uchlari yashil rangda 
ko'rsatilgan. 
 
Minimal kalit qiymatiga ega va MST-ga kirmagan (mstSET-da emas) 
vertikalni tanlang. 1 vertex tanlangan va mstSet-ga qo'shilgan. Endi mstSet {0, 1} 
bo'ladi. Qo'shni uchlarining kalit qiymatlarini yangilang. 1-sonning 8 qiymati 8 ga 
teng. 
 
Minimal kalit qiymatiga ega va MST-ga kirmagan (mstSET-da emas) 
vertikalni tanlang. Biz 7 ta vertexni yoki 2 ta vertexni tanlashimiz mumkin, vertex 
7 ni tanlaymiz. Endi mstSet {0, 1, 7} bo'ladi. 7-sonli ulashgan vertikallarning kalit 
qiymatlarini yangilang. 6 va 8-vertekslarning kalit qiymati cheklangan bo'ladi (mos 
ravishda 
1 
va 
7). 
Minimal kalit qiymatiga ega va MST-ga kirmagan (mstSET-da emas) 
vertikalni tanlang. Vertex 6 tanlangan. Endi mstSet {0, 1, 7, 6} bo'ladi. 6-sonli 
ulashgan tepaliklarning kalit qiymatlarini yangilang. 5 va 8-vertexlarning kalit 
qiymati yangilanadi. 
 
MstSet berilgan grafikning barcha uchlarini o'z ichiga olguncha yuqoridagi 
amallarni takrorlaymiz . Va nihoyat, biz quyidagi grafikni olamiz. 

---

 
Yuqoridagi 
algoritmni 
qanday 
amalga 
oshirish 
kerak? 
Biz MSTS ichiga kiritilgan uchlari to'plamini ifodalash uchun mstSet [] boolean 
massividan foydalanamiz. Agar mstSet [v] qiymati to'g'ri bo'lsa, v vertex MST 
tarkibiga kiradi, aks holda bo'lmaydi. Array tugmasi [] barcha vertikallarning kalit 
qiymatlarini saqlash uchun ishlatiladi. Ota tugunlarining indekslarini MST-da 
saqlash uchun yana bir ota-ona massivi. Ota-onalar massivi bu tuzilgan MSTni 
namoyish qilish uchun ishlatiladigan chiqish massividir. 
// A C++ program for Prim's Minimum
// Spanning Tree (MST) algorithm. The program is
// for adjacency matrix representation of the graph
#include
using namespace std;
// Number of vertices in the graph
#define V 5
// A utility function to find the vertex with
// minimum key value, from the set of vertices
// not yet included in MST
int minKey(int key[], bool mstSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
// A utility function to print the
// constructed MST stored in parent[]
void printMST(int parent[], int graph[V][V])
{
cout<<"Edge \tWeight\n";
for (int i = 1; i < V; i++)
cout<

---

}
// Function to construct and print MST for
// a graph represented using adjacency
// matrix representation
void primMST(int graph[V][V])
{
// Array to store constructed MST
int parent[V];
// Key values used to pick minimum weight edge in cut
int key[V];
// To represent set of vertices not yet included in MST
bool mstSet[V];
// Initialize all keys as INFINITE
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
// Always include first 1st vertex in MST.
// Make key 0 so that this vertex is picked as first vertex.
key[0] = 0;
parent[0] = -1; // First node is always root of MST
// The MST will have V vertices
for (int count = 0; count < V - 1; count++)
{
// Pick the minimum key vertex from the
// set of vertices not yet included in MST
int u = minKey(key, mstSet);
// Add the picked vertex to the MST Set
mstSet[u] = true;
// Update key value and parent index of
// the adjacent vertices of the picked vertex.
// Consider only those vertices which are not
// yet included in MST
for (int v = 0; v < V; v++)
// graph[u][v] is non zero only for adjacent vertices of m
// mstSet[v] is false for vertices not yet included in MST
// Update the key only if graph[u][v] is smaller than key[v]
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])

---

parent[v] = u, key[v] = graph[u][v];
}
// print the constructed MST
printMST(parent, graph);
}
// Driver code
int main()
{
/* Let us create the following graph
2 3
(0)--(1)--(2)
| / \ |
6| 8/ \5 |7
| / \ |
(3)-------(4)
9 */ 
int graph[V][V] = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };
// Print the solution
primMST(graph);
return 0;
}
// This code is contributed by rathbhupendra
Chiqish natijasi: 
Qirralarning vazni 
0 - 1 2 
1 - 2 3 
0 - 3 6 
1 - 4 5 
Yuqoridagi dasturning vaqt murakkabligi O (V ^ 2). Agar kirish grafigi 
ulashgan ro'yxat yordamida taqdim etilsa , unda Prim algoritmining vaqt 
murakkabligini ikkilik to'plash yordamida O (E log V) ga kamaytirish 
mumkin. Qarang qo'shnilik ro'yxati vakolatxonasi uchun jiddiy ning MST batafsil 
ma'lumot uchun.