|
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 + 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;
}
Ma’ruza savollari
Prim algoritmi ni tushuntirib bering
Kraskal algoritmini tushuntirib bering
Deykstra algoritmini namunaviy misol yordamida tushuntirib bering
Do'stlaringiz bilan baham: |
