О‘zbеkistоn rеspublikаsi аxbоrоt tеxnоlоgiyаlаri vа kоmmunikаtsiyаlаrini rivоjlаntirish vаzirligi

О‘ZBЕKISTОN RЕSPUBLIKАSI АXBОRОT TЕXNОLОGIYАLАRI VА KОMMUNIKАTSIYАLАRINI RIVОJLАNTIRISH VАZIRLIGI
MUHАMMАD АL-XОRАZMIY NОMIDАGI TОSHKЕNT АXBОRОT TЕXNОLОGIYАLАRI UNIVЕRSITЕTI SАMАRQАND FILIАLI
“Tеlеkоmmunikаtsiyа tеxnоlоgiyаlаri vа kаsb tа’limi” fаkultеti
“Tеlеkоmmunikаtsiyа injiniringi” kаfеdrаsi
5350100 – Telekommunikatsiya texnologiyalari yo‘nalishi
STT-20-01-guruhi talabasi Qayumov Ilhom
MUSTAQIL ISH


SАMАRQАND – 2022


TUBIGA QARAB QIDIRUV (DEPTH-FIRST SEARCH, DFS) ALGORITMI
Depth first search (DFS) algoritmi oson klassik graph algoritmlaridan biri bo’lib, u rekursiya ichida graph’dagi barcha vertex’larni tekshirib chiqishga yordam beradi. Aslida biz bu algoritmdan binary search tree‘dagi barcha ma’lumotlarni ko’rib chiqish uchun foydalanib, traverse() funksiyasini yozganmiz.
Depth first search algoritmining klassik deyilishiga sabab, qadimda undan labirintdan chiqish yo’lini topish uchun foydalanishgan. Labirintning boshlanish joyida g’altak – koptok qilib o’ralgan ipni ochib, yo’lni topishga kirishishgan. Berk ko’chaga kirib qolishganda, ip bo’yicha orqaga qaytib, kirilmagan yo’ldan davom ettirishgan. Shu tariqa ip orqali yurilgan yo’llarga qayta kirmaslik uchun ularni belgilab borishgan. Ip orqali yo’l topishni Trémaux maze exploration deb ham ataladi.
Labirint yechishni dasturda modellashtirish uchun labirintni graph’ga aylantiramiz. Bunda labirintning yo’llari edge’lar, chorrahalar vertex’lar bo’ladi.
Avvaldan aytib o’tish kerakki, Depth first search algoritmi labirintdan tez chiqib ketish uchun eng yaxshi yechim emas, u qisqa yo’lni topmaydi. Algoritm shunchaki «boshi oqqan ko’chaga» kirib chiqib, yo’l bor yo’qligini tekshiradi.
Kompyuterchasiga tushuntirganda, vertex’ning edge’lari bor yo’qligini tekshiradi, bor bo’lsa, har bir edge’dagi vertex’dan tekshiruvni davom ettiradi.
Algoritmning ishlash tartibi (vizualizatsiya)
Quyidagi graphning barcha vertex’larini tekshirib, qiymatlarini yig’ib chiqishimiz kerak bo’lsin.

DFS algoritmini A vertex’dan boshlaymiz. A topildi, uni «o’qilgan» qilib belgilaymiz (marked). Rekursiv funksiya stack tartibida ishlagani uchun, stack’ning tepasida A turipti, ya’ni funksiya A vertex uchun ishlamoqda.
A vertex bog’langan boshqa vertex’larni tekshiramiz. U B va G ga ulangan. Tekshiruvni B dan davom ettiramiz. Nima uchun B’dan? Aslida DFS algoritmi uchun B yoki G dan davom ettirishning ahamiyati yo’q. Esingizda bo’lsa graph uchun api yozganimizda, biz edge’larni Set ichida saqlagandik. Edge’ni o’qib olishda ham Set beradigan edge’lar bo’yicha DFS ishni davom ettiradi.

B stack’ning yuqorisida. Algoritm B’ga bog’langan tekshirilmagan vertex’larini tekshiradi. Ular C va G. C dan davom ettiradi.
C ga bog’langan tekshirilmagan vertex’lari yo’q. Stack’dagi C funksiya ishini to’xtatadi, demak C stackdan o’chiriladi.
Endi stack’ning yuqorisida B turipti. B ga bog’langan kirilmagan vertex – G.
G stack’ga qo’shiladi.
G stack’ning yuqorisida. G ga bog’langan kirilmagan bitta vertex bor – E.

E da kirilmagan ikki vertex bor: J va K. J dan davom ettiradi.
F ga bog’langan kirilmagan vertex’lar yo’q. F stackdan chiqariladi – rekursiyadagi F funksiya ishini tugatadi.
Graph yasash uchun bizda allaqachon Graph API bor. Kirilgan vertex’larni marked[] da belgilab, edgeTo[] ga esa vertex’ga qaysi vertex’dan kelinganini qo’shib boramiz. Shunda edgeTo[w] == v degani, w vertex’ga v vertex’dan kelinganini bildiradi. edgeTo dagi ma’lumotlar asosida biz bir vertex’dan ikkinchi vertex’ga yo’lni topishimiz mumkin.