Prim algoritmi Kruskal algoritmi
Tanlangan tugunlar to’plami
Download 76.9 Kb.
|
1 2
Bog'liq11-maruza
- Bu sahifa navigatsiya:
- Yuqoridagi graf uchun qo’shnilik matrisasi
- Kruskal algoritmi .
- O (M log N + N 2 )
- Mavzu yuzasidan savollar “Xasis” lik algoritmlari haqida tushuncha bering Prim algoritmini ishlash prinsipini tushuntirib bering
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 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 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 "< } 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 for (int i = 0; i < m; ++i) cin >> edges[i][1] >> edges[i][2] >> edges[i][0]; sort(edges.begin(), edges.end()); vector 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 “Xasis” lik algoritmlari haqida tushuncha bering Prim algoritmini ishlash prinsipini tushuntirib bering Kruskal algoritmini tushuntirib bering Download 76.9 Kb. Do'stlaringiz bilan baham: 
|
1 2