Algoritmlar va berilganlar strukturasi

OʻZBEKISTON RESPUBLIKASI OLIY VA O‘RTA MAXSUS
TA’LIM VAZIRLIGI
MIRZO ULUG‘BEK NOMIDAGI MILLIY UNIVERSITETININIG
JIZZAX FILIALI


AMALIY MATEMATIKA FAKULTETI
«KOMPYUTER ILMLARI VA DASTURLASHTIRISH» kafedrasi “ALGORITMLAR VA BERILGANLAR STRUKTURASI” FANIDAN
MUSTAQIL ISH

Mavzu: Grafdagi tugunlar orasidagi masfalarni topish.

Bajardi: “Axborot xavfsizligi” yoʻnalishi 2-kurs 30-21-guruh talabasi
Qarshiboyev Faryod
Tekshirdi: Tojiyev Ma’ruf.


Jizzax – 2023
Reja
1. Grafdagi tugunlar orasidagi masfalarni topish haqida tushincha.
2. Grafdagi tugunlar orasidagi masfalarni topish algortimlariga misollar.
3. Xulosa.
Grafdagi tugunlar orasidagi masofalar, bir grafdagi iki tugun orasidagi eng qisqa yo'l uzunligini ifodalaydi. Tugunlar grafning to'g'ri burchakli bo'lmagan bir tarmog'i elementlari hisoblanishi uchun ishlatiladi.
Bu masofalar ko'plab hisoblanishi mumkin, masalan, grafning barcha tugunlarini bitta tugunga bog'langan yoki qo'shimcha qurilmalar orqali ifodalaydi. Tugunlar orasidagi masofalar topish uchun bir qator algoritmlar mavjud, ularning bir qismi har xil graflar uchun optimal hisoblanadi, boshqalar esa uning tuzilmasiga qarab o'zgartirilishi kerak. Masofalar ko'payishi bilan birlikda, bu algoritmlar soni va murakkabligi katta bo'lishi mumkin. Shuning uchun, masofalar topish algoritmlari katta ma'lumotlar yoki shakllar uchun foydalaniladi.

BFS algoritmiga quydagi topshiriqni qarasak.