Prim algoritmi Kruskal 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 - .
Kruskal 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;}
Mavzu yuzasidan savollar

1. 
   “Xasis” lik algoritmlari haqida tushuncha bering
   
2. 
   Prim algoritmini ishlash prinsipini tushuntirib bering
   

Kruskal algoritmini tushuntirib bering