Eng qisqa yo‘l (Prima algoritmi, Kruskal algoritmi, Deykstriy algoritmi). Binar qidiruv daraxtlari. Ko‘p bosqichli graf

Eng qisqa yo‘l (Prima algoritmi, Kruskal algoritmi, Deykstriy algoritmi). Binar qidiruv daraxtlari. Ko‘p bosqichli graf.
Reja:

1. 
   Prima algoritmi kirish;
   
2. 
   Kruskal algoritmi haqida;
   
3. 
   Prima algoritmi, Kruskal algoritmi, Deykstriy algoritmlar tushunchasi.
   

1.Prim algoritm
n ta uchi va m qirrasi boʻlgan ogʻirlikdagi yoʻnaltirilmagan G graf berilgan. Ushbu grafikning barcha uchlarini bog'laydigan va shu bilan birga eng kichik vaznga (ya'ni qirra og'irliklarining yig'indisi) ega bo'lgan pastki daraxtini topish talab qilinadi. Pastki daraxt - bu barcha cho'qqilarni bog'laydigan qirralarning to'plami va istalgan uchdan boshqasiga aniq bitta oddiy yo'l bilan kirishingiz mumkin. Bunday pastki daraxt minimal kenglikdagi daraxt yoki oddiygina minimal kenglikdagi daraxt deb ataladi. Har qanday grafda n-1 qirralari bo'lishini tushunish oson. Tabiiy sharoitda bu muammo quyidagicha ko'rinadi: n ta shahar bor va har bir juftlik uchun ularni yo'l bilan ulash narxi ma'lum (yoki ularni bog'lab bo'lmasligi ma'lum). Barcha shaharlarni shunday bog'lash talab etiladiki, istalgan shahardan boshqasiga borish mumkin bo'ladi va shu bilan birga yo'l yotqizish xarajatlari minimal bo'ladi. Bu algoritm 1957 yilda ushbu algoritmni kashf etgan amerikalik matematik Robert Prim sharafiga nomlangan. Biroq, 1930 yilda bu algoritmni chex matematigi Voytex Yarnik kashf etgan. Bundan tashqari, Edsger Dijkstra ham 1959 yilda ulardan mustaqil ravishda ushbu algoritmni ixtiro qilgan.


2.Kruskal algoritmi. Dеykstra-Prim algoritmi VMY (vazni minimal yig’indisi) ni qurishni boshlang’ich grafning ixtiyoriy tugunidan boshlaydi va daraxtning qurilgan qismini tobora kеngaytirib boradi. Ushbu algoritmdan farqli ravishda Kruskal algoritmi asosiy e'tiborni graf tomonlariga qaratadi. Bunda ishni bo’sh grafdan boshlab, unga tomonlarini ular vaznining o’sib borish tartibida kеtmakеt qo’shib boradi. Bu jarayon grafga kiruvchi barcha tugunlar o’zaro bog’langunga qadar davom etadi. Agar tomonlarni qo’shib olish jarayoni barcha tugunlar o’zaro bog’langunga qadar tugatilsa, boshlan?ich grafning to’liq bog’lanmagan ekanligi kеlib chiqadi. Grafning VMY (vazni minimal yig’indisi) ini anqlashda ishlatiluvchi “ochko’z” algoritm tugunlar orasidagi eng qisqa yo’lni aniqlashga yaramaydi, chunki har bir vadvmdv u faqat bitta tomon uzunligini hisobga oladi. Agar ushbu algoritmni har qadamda boshlang’ich tugundan chеgara tugungacha bo’lgan eng qisqa yo’lning qismini tashkil qiluvchi tomonni tanlaydigan qilib o’zgartirsak, kеrakli natijaga erishish mumkin bo’ladi