Axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti nurafshon filiali

Download 243.19 Kb.
bet	1/4
Sana	01.05.2023
Hajmi	243.19 Kb.
	#55178

1 2 3 4

Bog'liq
Axborot texnologiyalari va kommunikatsiyalarini rivojlantirish v
Mustaqil ish mavzularining taqsimlanishi, 3-amaliy (1), 1 5A110102 Talimda axborot texnologiyalari магистратура 2021 2022 (1), Ma�ruza 22. Sut emizuvchilar ekologiyasi va evolyutsiyasi. Reja-3, Graflar nazariyasi. Graflar nazariyasiningasosiy tushunchalari. , test[3], 8-Amaliy ish, Kibrxavfsizlik dedlayin maruza, 1. Foiz stavkasining oshishi ga olib keladi-fayllar.org (2), Kurs ishi, Bolalar folklori, Boshlang\'ich sinflarda grammatik tahlilni o\'tkazish metodikasi.”-fayllar.org, Mustaqil ish AUMY fanidan, Boshlang’ich ta’limda aktdan foydalanish fanidan maruzlar matni-fayllar.org (3)

Bajardi
1-qadam

AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH 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: 610-21
Bajardi: Xashimbayev Javohir
Tekshirdi: Tosheva Muhabbat

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.

Download 243.19 Kb.

1 2 3 4

Download 243.19 Kb.