Prim algoritmi Kruskal algoritmi


Tanlangan tugunlar to’plami



Download 456,21 Kb.
bet2/2
Sana28.06.2022
Hajmi456,21 Kb.
#712210
1   2
Bog'liq
11-maruza

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 ABE 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 + N2) 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 + N2) 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

Download 456,21 Kb.

Do'stlaringiz bilan baham:
1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish