19. Прима-Дeйкстра алгoритми. Вақт бўйича самарадoрлигини баҳoлаш

19.Прима-Дeйкстра алгoритми. Вақт бўйича самарадoрлигини баҳoлаш

Primning minimal tejamkor daraxti (MST) | Ochko'z Algo-5

Biz Kruskalning minimal tejamkorlik daraxti uchun algoritmini muhokama qildik . Kruskalning algoritmi singari, Prim algoritmi ham ochko'z algoritmdir . U bo'shashgan daraxtdan boshlanadi. G'oya ikkita vertikal to'plamni ushlab turishdir. Birinchi to'plamda allaqachon MST-ga kiritilgan uchlari mavjud, ikkinchisida esa hali mavjud bo'lmagan uchlari mavjud. Har qadamda, u ikkita to'plamni bog'laydigan barcha qirralarni ko'rib chiqadi va bu qirralarning minimal og'irligini tanlaydi. Yonni tanlaganingizdan so'ng, u chetning boshqa oxirgi uchini MST o'z ichiga olgan to'plamga o'tkazadi.
Grafikdagi ikkita uch uchini bog'laydigan qirralar guruhi grafik nazariyasida kesilgan deb nomlanadi . Shunday qilib, Prim algoritmining har bir bosqichida biz kesmani topamiz (ikkita to'plam, bittasida allaqachon MST kiritilgan va boshqa vertikal qismlar mavjud), kesmaning eng kam og'irligini tanlang va bu uchni MST Set-ga qo'shing. (allaqachon kiritilgan uchlarini o'z ichiga olgan to'plam).
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.
¹Prim algoritmi haqida batafsil video.