Ma’lumotlar bazasini administratorlash va xavfsizligini ta’minlash

Graflarda ko‘ruv algoritmlari. Eniga qarab qidiruv (Breadth first search, BFS) algoritmi. Tubiga qarab qidiruv (Depth-first search, DFS) algoritmi.

015-guruh

Eshqobilov Azamat

Reja:

• Graflarda ko`ruv algoritmi
• Graflarda ko`ruv algoritmida asosiy qadamlar

3. Eniga qarab qidiruv
4. BFS qanday ishlaydi?
5. Tubiga qarab qidiruv
6. DFC qanday ishlaydi?

Graflarda ko`ruv algoritmi

Ko'ruv algoritmi, graf tuzulmasidagi minimum ko'plab qanchaliklar ustunlarini topish uchun ishlatiladigan bir algoritmdir. Bu algoritmning asosiy maqsadi, berilgan graf tuzulmasida hammasi bir-biriga ulangan bo'lgan butun qanchaliklarni (ustunlarni) ko'rinishini topishdir.
Bu algoritmning asosiy qadamalari quyidagilardan iborat:

• Graf tuzulmasidagi barcha qanchaliklarga alohida bo'shliklar beriladi.
• Barcha uchunlar orasidan bitta uchun tanlanadi.
• Tanlangan uchunning hammasi bilan ulangan butun qanchaliklarga alohida bo'shliklar beriladi.
• Qanchaliklar ro'yxati bo'sh bo'lmaguncha, qayta 2-3 qadamlar bajariladi, lekin har bir qanchalik uchun tanlovni o'zgartirib yuborish bilan biriktiriladi.
• Qanchaliklar ro'yxati bo'sh bo'lganda, topilgan minimum ko'plab qanchaliklar ustunlarining ro'yxati qaytariladi.

Graflarda ko`ruv algoritmida asosiy qadamlar
Eniga qarab qidiruv
Breadth First Search (BFS) algoritmi bir qator mezonlarga javob beradigan tugun uchun grafik ma'lumotlar strukturasini qidirish uchun ishlatiladi. U grafikning ildizidan boshlanadi va keyingi chuqurlik darajasidagi tugunlarga oʻtishdan oldin joriy chuqurlik darajasidagi barcha tugunlarga tashrif buyuradi.
Ildizdan boshlab, avval ma'lum bir darajadagi barcha tugunlarga tashrif buyuriladi va keyin barcha tugunlarga tashrif buyurilgunga qadar keyingi darajadagi tugunlar o'tkaziladi.
Buning uchun navbat ishlatiladi. Joriy darajadagi barcha qo'shni ko'rilmagan tugunlar navbatga suriladi va joriy darajadagi tugunlar tashrif buyurilgan va navbatdan chiqariladi.
BFS qanday ishlaydi?

Tubiga qarab qidiruv

Grafik uchun Birinchi chuqurlik (yoki DFS) Daraxtning chuqurlikdagi birinchi oʻtishiga oʻxshaydi. Bu erda yagona narsa shundaki, daraxtlardan farqli o'laroq, grafiklarda tsikllar bo'lishi mumkin (tugunga ikki marta tashrif buyurish mumkin). Tugunga bir necha marta ishlov bermaslik uchun mantiqiy tashrif buyurilgan massivdan foydalaning. Grafikda bir nechta DFS o'tishlari bo'lishi mumkin.
Chuqurlikdagi birinchi qidiruv - bu daraxt yoki grafik ma'lumotlar tuzilmalarini kesib o'tish yoki qidirish uchun algoritm. Algoritm ildiz tugunidan boshlanadi (grafikda ba'zi bir ixtiyoriy tugunni ildiz tugun sifatida tanlash) va orqaga qaytishdan oldin har bir filial bo'ylab iloji boricha o'rganadi.
DFC qanday ishlaydi?
XULOSA
Men bu mavzudan uzimga erak buladigan qidiruv usullari eniga (Breadth first search, BFS) algoritmi va tubiga qarab qidiruv (Depth-first search) algoritmi haqida bilib oldim. Bu qidiruvlar malumotlarni oson qidirishda yordam berar ekan.

Foydalanilgan adabiyotlar:

https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/
https://prezi.com/p/5rsjdoyissnq/6graflar-nazariyasi-elementlari-va-otish-algoritmlari/
https://oefen.uz/uz/documents/diplom-ishlar/umumiy/graflarda-eng-qisqa-masofani-topish-algoritmlari
https://genderi.org/algoritmlar-va-berilganlar-strukturalari.html?page=7
THE END