Algoritmdan nazorat savollariga javoblar Algoritm nima

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.