Prim algoritmi Kraskal algoritmi

Tanlangan tugunlar to’plami	(u,v) qirra	V/U tanlanmagan 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}
	{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.

Quyida Prim algoritmi keltirilgan.
1-dastur. Prim algoritmi
procedure Prim ( G: graf; var T: qirralar to’plami );
var
U: qirralar to’plami;
u, v: qirra;
begin
T:= ø;
U:= {1};
while U ≠ V do begin
eng kam narxli va u U va v V\U bo’lgan (u, v) qirrani topish;
T:= T {u, V));
U:= U {v}
end
end; { Prim }
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
Dastur
#include
using namespace std;


int main()
{
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0}, min, mincost=0,cost[10][10];
int path[100]={0}; //ushbu massivda yulni tashkil qiladigan tugunlar yoziladi
int path_index=0;


cout<<"Tugunlar sonini kiriting "; cin>>n;
cout<<"Qushnilik matritsasini kiriting\n";
for(i=0;i
for(j=0;j
{
cin>>cost[i][j];
if(cost[i][j]==0)
cost[i][j]=999; // 999 - eto chto-tipa beskonechnosti. Doljno bыt bolshe chem znacheniya vesa kajdogo iz reber v grafe
}
visited[0]=1;
cout<<"\n";


while(ne < n)
{
for(i=0, min=999; i
for(j=0;j
if(cost[i][j]< min)
if(visited[i]!=0)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0)
{
path[path_index]=b;
path_index++;
ne++;
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
cout<<"\n";
cout<<1<<" --> ";
for (int i=0;i
{
cout<

if (i ";
}
cout<<"\n Minimal narx "<


return 0;
}

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 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.
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.
3. INITIAL(A, v, S) operatori naborda faqat v bo’g’imdan iborat A nomli komponentni yaratadi.
Ushbu algoritm O (M log N + N²) 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²) kelib chikadi.
Dastur ko’rinishi quyidagicha buladi:
int n, m;
cin >> n >> m;
vector > edges(m, vector(3));
for (int i = 0; i < m; ++i)
cin >> edges[i][1] >> edges[i][2] >> edges[i][0];
sort(edges.begin(), edges.end());
vector comp(n);
for (int i = 0; i < n; ++i)
comp[i] = i;
int ans = 0;
for (auto & edge: edges)
{
int weight = edge[0];
int start = edge[1];
int end = edge[2];
if (comp[start] != comp[end])
{
ans += weight;
int a = comp[start];
int b = comp[end];
for (int i = 0; i < n; ++i)
if (comp[i] == b)
comp[i] = a;
}
}


// Dijkstra algoritmi.
#include
using namespace std;
// Graf uchlari soni
#define V 9
int shortest_path(int dist[], int n)
{
cout<<"Uchlar "<<"\t"<<"Masofa\n";
for (int i = 0; i < V; i++)
cout<<" \t\t \n"<< i<<" \t\t "<
}
// minimal masofani hisoblash
int minDist(int dist[], bool Set[])
{
int min = INT_MAX, min_index;
for (int i = 0; i < V; i++)
if (Set[i] == false && dist[i] <= min)
min = dist[i], min_index = i;
return min_index;
}
// Boshqa uchlargacha eng qisqa yo'llarni aniqlash
void Dijkstra(int g[V][V], int src)
{
int dist[V];
bool Set[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, Set[i] = false;
dist[src] = 0;
for (int c = 0; c < V- 1; c++)
{
int u = minDist(dist, Set);
Set[u] = true;
for (int j = 0; j < V; j++)
if (!Set[j] && g[u][j] && dist[u] != INT_MAX && dist[u]+ g[u][j] < dist[j])
{
dist[j] = dist[u] + g[u][j];
}
}
shortest_path(dist, V);
}
// asosiy funksiya
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int G[V][V] = {
{ 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 }};
Dijkstra(G, 0);
return 0;
}
Ma’ruza savollari

1. 
   Prim algoritmi ni tushuntirib bering
   
2. 
   Kraskal algoritmini tushuntirib bering
   
3. 
   Deykstra algoritmini namunaviy misol yordamida tushuntirib bering
   

Bu darsimizda sizlar bilan algoritm murakkabligini qanday baholash va bu narsa nima uchun muhimligi haqida to'xtalib o'tamiz. Hamda O-notatsiysa (O(n), O(n^2)) nimani anglatishini ko'rib o'tamiz.

Odatda, dasturlash masalalarini yechishda bir nechta yechim mavjud bo'ladi. Ular bir-biridan ishlash tezligi, xotiradan qancha joy olishi yoki tushunish murakkabligi bilan farqlanadi. Bunda, asosan, ikki xil tushuncha mavjud: algoritmning vaqt bo'yicha murakkabligi va xotira bo'yicha murakkabligi.

Algoritmning vaqt bo'yicha murakkabligi - bu uning ishlash vaqtini unga kiruvchi (input) ma'lumot(lar)ga nisbatan o'zgarishiga aytiladi.

Algoritmning xotira bo'yicha murakkabligi - huddi yuqoridagi kabi, algoritm ishlashi uchun unga kerak bo'lgan xotira hajmini (operativ xotiradan olinadigan joy) kiruvchi (input) ma'lumot(lar)ga nisbatan o'zgarishiga aytiladi.

Dasturiy masalalar yechishda yuqoridagi ikkita omil eng muhimlari sanaladi. Shuning uchun sizning yechimingiz qanday holatdlarda o'rtacha qancha vaqt ishlashi va operativ xotiradan qancha joy egallashini bilish muhim hisoblanadi.

Dasturlash musobaqalarida, asosan, birinchi jihatga ko'proq e'tibor qaratiladi. Lekin aniq vaqt, judayam ko'p omillarga bog'liq: kompyuter qurilmalari, protsessori, operatsion tizim va hokazolarga. Shuning uchun ham bizga faqat uning nazariy jihatdan ishlash vaqtini baholash qiziq. Bunda O() (O - notatsiya)dan foydalaniladi.

O notatsiya ta'rifiga o'tishdan oldin bitta misol keltirib o'tamiz:

N ta elementli massivdan x elementni qidirish kerak bo'lsin. Oddiy yechim, chiziqli qidiruvni ko'ramiz, ya'ni massiv har bir elementni berilgan elementga birma-bir solishtirib ko'ramiz.

for i : 1 to length of A

if A[i] is equal to x
return TRUE
return FALSE
Bunda har bir amal o'zgarmas c vaqt sarflaydi deb hisoblaylik. Biz algoritm murakkabligini hisoblaganda eng yomon holatni hisobga olishimiz kerak. Bu holatda esa x element massivda yo'q holat eng yomon holat hisoblanadi, ya'ni massivning barcha N ta elementi ko'rib chiqilishi kerak. Umumiy holatda, algoritm ishlashi uchun N*c + c (N ta if uchun va bitta return uchun). Algoritm murakkibligini baholaganda konstantalar e'tiborga olinmaydi va bu yuqoridagi algoritm murakkabligini O(N) deb hisoblash mumkin.

Ya'ni kiruvchi massiv hajmi oshib borgan sari algoritmimiz ishlash vaqti ham N ga bog'liq oshib boradi (bu holatda chiziqli nisbatda). Endi ta'riflarga o'tadigan bo'lsak:

O-notatsiya

Ta’rif: Agar shunday konstanta c soni mavjud bo’lsaki, bunda barcha natural n sonlari uchun f(n)≤c*g(n) shart bajarilsa, f funksiya g funksiyadan tez o’smaydi va f(n)≤O(g(n)) ko’rinishida yoziladi.

O-notatsiya yuqori chegarani, ya'ni eng yomon holatni baholash uchun ishlatiladi. Shu sababdan ham dasturlash masalalarini yechishda O-notatsiyadan eng keng foydalaniladi.

Ω-notatsiya (Omega notatsiya)

Ta'rif: Agar shunday konstanta c soni mavjud bo’lsaki, bunda barcha natural n sonlari uchun f(n)≥c*g(n) shart bajarilsa, g funksiya f funksiyadan tez o'smaydi va f(n)≥Ω(g(n)) ko’rinishida yoziladi.

Ω-notatsiya pastki chegarani ifodalashda ishlatiladi.

Θ-notatsiya (Teta notatsiya)

Ta'rif: Agar shunday konstanta c soni mavjud bo’lsaki, bunda barcha natural n sonlari uchun f(n)=c*g(n) shart bajarilsa, f funksiya g funksiya bilan bir xilda o'sadi va f(n)=Θ(g(n)) ko’rinishida yoziladi.

Yanayam soddaroq tushunish uchun quyidagi jadvalni keltiramiz

Darsimizning ikkinchi qismida algoritm murakkabligini hisoblashdagi asosiy qoidalarni va dasturlash olimpiadalarida eng ko'p uchraydigan murakkabliklarni ko'rib chiqamiz va solishtirib ko'ramiz.

Maqolani foydali deb hisoblasangiz uni do'stlaringizga ham ulashing.