|
Algoritmlarni loyhalash ”fanidan mustaqil ishi qabullagan: ass. M. A. Artikbayev Bajargan: J. M. Sadullayev Nukus-2024 Mavzu: Xoffman daraxtlari. Reja
|
| bet | 2/5 | | Sana | 16.05.2024 | | Hajmi | 118,78 Kb. | | #238888 |
Bog'liq Sadullayev Javlonbek Algaritmlarni loyhalashKruskal Algoritmi
Algoritm g`oyasini ifodalaylik. Avval daraxt qirralarining to`plami bo`sh deb e’lon qilinadi. Shundan so`ng mumkin bo`lgunga qadar keyingi amal bajariladi: barcha qirralardan, ularni mavjud to`plamga qo`shilishi sikl paydo bo`lishiga olib kelmaydigan qirralardan, eng arzon (engkamxarajatli) qirrasi tanlab olinadi va mavjud to`plamga qo`shib qo`yiladi. Bunday qirralar qolmaganida, algoritm tugallanadi va biz dastlabki grafni barcha uchlariga ega bo`lgan graf ostisini hosil qilamiz. Ushbu graf ostisida siklar bo`lmasligidan, u eng arzon (eng kam harajatli)daraxt bo`lib, uning boshqacha nomini ostov daraxti deb yuritiladi. Algoritmni yaqqol tasavvurini misolda amal ga oshiramiz va barcha jarayonni bosqichma-bosqich sxematik tarzda ifodalaymiz. Dastlabki graf 11.1.rasmda keltirilgan.
11.1.rasm
B D
5 10 C 7
A 8 12 9
6 15 E
G 13 11
8 F
Grafning xar bir qirrasi ma’lum vaznga ega bo`lib, ostov daraxtini qurishda biz aynan qirralar vaznidan kelib chiqamiz. Buning uchun qirralarni vaznlari bo`yicha tartiblaymiz. Engarzon 5 qiymatli qirra A B daraxt to`plamining birinchi elementi bo`ladi va keyngi AG, CD, AC, GF, DE qirralar qiymati bo`yicha daraxtga qo`shib boriladi
1chibosqichchizmaAB nitanlash
2chibosqichchizmaAGniqo`shish
3chibosqichchizmaCDniqo`shish
4chibosqichchizmaAC, GFlarniqo`shish
5chibosqichchizmaDEniqo`shish.
Qolgan qirralardan ixtiyoriy sini berilgan daraxtga qo`shilishi sikllar xosil bo`lishiga olib keladi. Demak aynan shu daraxt qidirilayotgan ostov daraxti bo`ladi. Bayonimiz to`liq bo`lishi uchun dastlabki grafni shunday tasvirlaymizki, ostov daraxtining qirralari tekis -uzluksiz chiziqlar bilan, qolgan qirralar punktir chiziqlar bilan chizilgan bo`ladi.
11.2 rasm.
D
B
A C
E
F
Grafning ostov daraxtining qo`rishning yana bir usulini ko`raylik.
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Algoritmlarni loyhalash ”fanidan mustaqil ishi qabullagan: ass. M. A. Artikbayev Bajargan: J. M. Sadullayev Nukus-2024 Mavzu: Xoffman daraxtlari. Reja
|
