Algoritmdan nazorat savollariga javoblar Algoritm nima


Chuqurlik bo’yicha izlash algoritmi(dfs)



Download 4,28 Mb.
bet51/61
Sana31.12.2021
Hajmi4,28 Mb.
#254919
1   ...   47   48   49   50   51   52   53   54   ...   61
Bog'liq
2 5355268973329911567

40. Chuqurlik bo’yicha izlash algoritmi(dfs).

Chuqurlik bo’yicha izlash(inglizcha Depth-first search, DFS) graflar nazariyasining eng muhm algoritmlaridan biri. Chuqurlik bo’yicha izlash algoritmi strategiyasi uning nomiga mos ravishda grafda chuqurlik bo’yicha qancha borish mumkin bo’lsa shuncha yuradi, toki yo’l qolmagunga qadar. Algoritm rekursiv ko’rinishda bo’ladi: qaralayotgan uchdan chiquvchi barcha uchlarni ko’rib chiqamiz. Agar bu qirra hali ko’rilmagan uchga olib borsa, izlash shu ko’rilmagan uch orqali davom ettiriladi va unga qo’shni bo’lgan uchlar ko’rib chiqiladi. Agar joriy uchdan chiquvchi va hali ko’rilmagan uchga olib boruvchi qirra qolmasa u holda orqaga qaytish sodir bo’ladi. Joriy uchga qaysi uch orqali kelgan bo’lsa huddi shu uchga qaytariladi va u orqali qolgan qirralar ko’rilishi davom ettiriladi. Ohir oqibatda dastlab izlash boshlangan uchga qaytib keladi va undan ham chiqishda berilgan grag qismi orqali to’liq o’tib bo’lingan bo’ladi. Agar bundan so’ng ko’rilmagan biror uch bo’lsa izlashni shu uch orqali davom ettirish kerak.




6

1

3

5

4

2
Bu aniq misolda ko’rib chiqaylik, bizga quyidagicha graf berilgan:

Bu grafni chuqurlik bo’yicha izlash tartibida o’tib chiqamiz, buning uchun belgilashlar kiritaylik:





  • Hozir biz turgan uch.



−Tashrif buyurilgan(ko’rilgan) lekin hali aktiv uch, ya’ni undan hali ortga qaytilmagan.




−Hali ko’rilmagan uch






−Undan chiqib ketilgan uch.


−Hozir qaralayotgan qirra

Grafni chuquurlik bo’yicha izlashni 1-uchdan boshlaymiz va qo’shnilarni nomerlari kichik tartibda ko’rin chiqamiz. Qirralarni qanday tartibda ko’rishning ahamiyati yo’q.



  1. 1-uchdan boshlaymiz. Datlab ikkinchi uch bilan bo’g’laydigan qirra orqali o’tamiz:


4

2) 2-uchdan chiquvchi uch yo’q, shuning uchun undan orqaga ya’ni 1-uchga qaytamiz.

4

4

4


3)1-uchdan chiquvchi qirra orqali 3-uchga o’tamiz.




4) 3 – uchdan 4-uchga o’tamiz:


5) 4 – uchdan 2-uchga o’tadigan qirrani qaraymiz, lekin 2-uch allaqachon ko’rilgan, shuning uchun u bo’yicha o’tmaymiz va orqaga qaytamiz:




6) 3-uch dan navbatdagi qirra orqali 5 uchga o’tamiz:



7) 5-uchdan chiquvchi va 4-uchga olib boruvchii qirrani qaraymiz, lekin 4-uch allaqachon ko’rilgan.


Natijada barcha uchlar va barcha qirralar ko’rib chiqiladi. Demak algoritmning usumiy ishlash vaqti O(n+m). Bu yerda n – uchlar soni, m – qirralar soni.




Download 4,28 Mb.

Do'stlaringiz bilan baham:
1   ...   47   48   49   50   51   52   53   54   ...   61




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish