1. Dasturiy ta’minot va uning turlari

97 Kruskal algoritmini realizatsiya qilish
Kruskal algoritmi. Dеykstra-Prim algoritmi MOD 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еtma-kе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.
98. Graflarda minimal yoʻlni topish algoritmini realizatsiya qiling
Grafikdagi grafik va manba cho'qqisi bo'lsa, berilgan grafikdagi manbadan barcha cho'qqilarga eng qisqa yo'llarni toping.
Dijkstra algoritmi Primning minimal oraliqli daraxt algoritmiga juda o'xshaydi. Primning MST-ga o'xshab, biz ildiz sifatida berilgan manba bilan SPT (eng qisqa yo'l daraxti) ni yaratamiz. Biz ikkita to'plamni saqlaymiz, bir to'plam eng qisqa yo'l daraxtiga kiritilgan cho'qqilarni o'z ichiga oladi, boshqa to'plam hali eng qisqa yo'l daraxtiga kiritilmagan cho'qqilarni o'z ichiga oladi. Algoritmning har bir bosqichida biz boshqa to'plamdagi (hali kiritilmaganlar to'plami) va manbadan minimal masofaga ega bo'lgan cho'qqini topamiz.
Quyida bitta manba cho'qqisidan berilgan grafikdagi barcha boshqa cho'qqilarga eng qisqa yo'lni topish uchun Dijkstra algoritmida qo'llaniladigan batafsil qadamlar keltirilgan.
Algoritm
1) Eng qisqa yo'l daraxtiga kiritilgan, ya'ni manbadan minimal masofa hisoblangan va yakunlangan cho'qqilarni kuzatib boruvchi sptSet to'plamini (eng qisqa yo'l daraxti to'plami) yarating. Dastlab, bu to'plam bo'sh.
2) Kirish grafigidagi barcha cho'qqilarga masofa qiymatini belgilang. Barcha masofa qiymatlarini INFINITE sifatida boshlang. Manba cho'qqisiga masofa qiymatini 0 sifatida belgilang, shunda u birinchi bo'lib tanlanadi.
3) SptSet barcha cho'qqilarni o'z ichiga olmaydi
….a) sptSet da mavjud boʻlmagan va minimal masofa qiymatiga ega boʻlgan u uchini tanlang.
….b) u ni sptSetga kiriting.