Raqamli texnologiyalar vazirligi

RAQAMLI TEXNOLOGIYALAR VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
NURAFSHON FILIALI


Ma`lumotlar tuzilmasi va algoritmlar fanidan

Mustaqil ish
Mavzu: Tubiga qarab qidiruv (Depth-first search, DFS) algoritmi.
Guruh: 210-22
Bajardi: Ochilov Diyorbek
Tekshirdi: Turg’unaliyev Shoxruz

TOSHKENT – 2022

Tubiga qarab qidiruv (Depth-first search, DFS) algoritmi
Reja:
1. Tubiga qarab qidiruv (Depth-first search, DFS) nima?
2) Depth-first search qanday ishlaydi.(examples)
3)Xulosa.

Tubiga qarab qidiruv (DFS) - bu daraxt yoki grafikdan o'tish uchun ishlatiladigan yana bir usul.

DFS ildiz tuguni yoki boshlang'ich tugunidan boshlanadi va keyin grafik yoki daraxtga chuqurroq kirib, joriy tugunning qo'shni tugunlarini o'rganadi. Bu shuni anglatadiki, DFS-da tugunlar bolalari bo'lmagan tugunga duch kelguniga qadar chuqurlik bo'yicha o'rganiladi.
Barg tuguniga erishilgandan so'ng, DFS orqaga qaytadi va shunga o'xshash tarzda yana bir nechta tugunlarni o'rganishni boshlaydi.

DFS algoritmi

• 
  1-qadam: Daraxtning ildiz tugunini yoki boshlang'ich tugunini yoki grafikni stekka joylashtiring.
  
• 
  2-qadam: Yuqori elementni stekdan oching va uni tashrif buyurilgan ro'yxatga qo'shing.
  
• 
  3-qadam: Tashrif buyurilgan tugunning barcha qo'shni tugunlarini toping va hali tashrif buyurmaganlarini stekka qo'shing.
  
• 
  4-qadam: Stek bo'sh bo'lguncha 2 va 3-bosqichlarni takrorlang.
  
• 
  Endi grafikning DFS o'tishini tasvirlaylik. Aniqlik maqsadida biz BFS rasmida ishlatgan grafikdan foydalanamiz.
  

0 boshlang'ich tugun yoki manba tuguni bo'lsin. Birinchidan, biz uni tashrif buyurilgan deb belgilaymiz va tashrif buyurilgan ro'yxatga qo'shamiz. Keyin biz uning barcha qo'shni tugunlarini stekka suramiz.

• Keyinchalik, biz ishlov berish uchun qo'shni tugunlardan birini olamiz, ya'ni stekning ustki qismi 1. Biz uni tashrif buyurilganlar ro'yxatiga qo'shish orqali tashrif buyurilgan deb belgilaymiz. Endi 1 ning qo'shni tugunlarini qidiring. 0 allaqachon tashrif buyurilganlar ro'yxatida bo'lgani uchun biz uni e'tiborsiz qoldiramiz va stekning yuqori qismi bo'lgan 2 ga tashrif buyuramiz.

• 
  Keyin biz 2-tugunni tashrif buyurilganidek belgilaymiz. Uning qo'shni tuguni 4 stekka qo'shiladi.
  

• 
  Keyingi, biz belgilash 4 tashrif buyurdi, deb suyakka yuqori bo'lgan. 4-tugunda allaqachon tashrif buyurilgan qo'shni sifatida faqat 2-tugun mavjud, shuning uchun biz uni e'tiborsiz qoldiramiz.
  

• 
  Ushbu bosqichda stekda faqat 3-tugun mavjud. Uning qo'shni tugun 0 allaqachon tashrif buyurgan, shuning uchun biz uni e'tiborsiz qoldiramiz. Endi biz 3 ni tashrif buyurilganidek belgilaymiz.
  

Endi to'plam bo'sh va tashrif buyurilgan ro'yxat berilgan grafikning birinchi chuqurlikdan o'tish ketma-ketligini ko'rsatadi.

Agar biz berilgan grafik va o'tish ketma-ketligini kuzatsak, DFS algoritmi uchun biz haqiqatan ham grafikni chuqurlik bo'yicha bosib o'tamiz va keyin yangi tugunlarni o'rganish uchun yana orqaga qaytamiz.