Mavzu: Tubiga qarab qidiruv (depth-first search, dfs) algoritmi Bjardi: Xurramov Bobur Tekshirdi: Tosheva Muhabbat Maxkamovna

Mavzu:Tubiga qarab qidiruv (depth-first search, dfs) algoritmi Bjardi:Xurramov Bobur Tekshirdi:Tosheva Muhabbat Maxkamovna

Chuqurlik Birinchi qidiruv algoritmi | DFS misoli

• Chuqurlik birinchi qidiruv -
• Depth First Search yoki DFS - bu grafik o'tish algoritmidir.
• U grafikni tizimli ravishda aylanib o'tish yoki qidirish uchun ishlatiladi.
• DFS iloji boricha grafikda "chuqurroq" qidiradigan strategiyadan foydalanadi.
• Chuqurlikdagi birinchi qidiruvni amalga oshirishda stack ma'lumotlar strukturasidan foydalaniladi.

DFS misoli

• Quyidagi grafikni ko'rib chiqing –
• Yuqoridagi grafikning chuqurlikdagi birinchi qidiruv o'tish tartibi -
• A, B, E, F, C, D

Chuqurlikdagi birinchi qidiruv algoritmi

• DFS (V, E)
• V[G] dagi har bir u tepasi uchun
• rang qilish[v] ← OQ
• p[v] ← NIL
• vaqt ← 0
• V[G] dagi har bir v tepasi uchun
• do if color[v] ← OQ
• keyin Depth_First_Search(v)

• Depth_First_Search (v)
• rang[v] ← KUZI
• vaqt ← vaqt + 1
• d[v] ← vaqt
• v ga ulashgan har bir cho'qqi uchun
• do if color[u] ← OQ
• p[u] ← v
• Depth_First_Search(u)
• rang[v] ← QORA
• vaqt ← vaqt + 1
• f[v] ← vaqt

Qadam-01

• Grafikning har bir cho'qqisi uchun 4 ta o'zgaruvchini yarating va saqlang.
• Grafikning har qanday 'v' cho'qqisi uchun bu 4 o'zgaruvchi:
• 1. rang[v]-
• Bu o'zgaruvchi berilgan vaqt nuqtasida "v" cho'qqisining rangini ifodalaydi.
• Bu o'zgaruvchining mumkin bo'lgan qiymatlari - OQ, KULI va QORA.
• Tepaning OQ rangi uning hali kashf etilmaganligini bildiradi.
• Cho'qqining KUZ rangi uning aniqlanganligini va qayta ishlanayotganligini bildiradi.
• Cho'qqining QORA rangi uning to'liq qayta ishlanganligini bildiradi.

• 2. n[v]-
•  Bu o'zgaruvchi "v" cho'qqisining oldingi qismini ifodalaydi.
• 3. d[v]-
• Bu oʻzgaruvchi “v” choʻqqisi topilganda vaqt tamgʻasini ifodalaydi.
• 3. f[v]-
• Bu o'zgaruvchi "v" cho'qqisini qayta ishlash tugallangan vaqt tamg'asini ifodalaydi.

Qadam-02

• Grafikning har bir cho'qqisi uchun o'zgaruvchilarni ishga tushiring:
• rang [v] = OQ
• p [v] = NIL
• vaqt = 0 (taymer vazifasini bajaradigan global o'zgaruvchi)

Qadam-03

• Chuqurlik_birinchi_qidiruv (G,v)
•  
• 1. rang[v] = KUZI
• 2. vaqt = vaqt + 1
• 3. d[v] = vaqt
• 4. "v" ning har bir qo'shni OQ cho'qqisi "u" uchun p[u] = v ni o'rnating va Depth_First_Search (G,u) ni chaqiring.
• 5. rang[v] = QORA
• 6. vaqt = vaqt + 1
• 7. f[v] = vaqt

• DFS vaqt murakkabligi -
•  
• Chuqurlikdagi birinchi qidiruvning umumiy ish vaqti th (V+E).
•  
• DFS-dagi qirralarning turlari -
•  
• Har qanday G grafigini DFS o'tkazgandan so'ng, uning barcha qirralari quyidagi 4 sinfdan biriga joylashtirilishi mumkin:

• Daraxt chekkasi
• Orqa chekka
• Oldinga chekka
• Cross Edge

• 1. Daraxt cheti-
• Daraxt qirrasi - bu DFS daraxtiga kiritilgan chekka.
• 2. Orqa tomon -
• "U" cho'qqisidan uning ajdodlaridan biri "v"gacha bo'lgan chekka orqa chekka deyiladi.
• O'z-o'zidan pastadir orqa tomon sifatida qabul qilinadi.
• 3. Oldinga tomon –
• “u” cho‘qqisidan uning avlodlaridan biri “v”gacha bo‘lgan chekka oldinga tomon deyiladi.
• Oldinga tomon qachon aniqlanadi -
• DFS tashrifni "u" cho'qqisidan "v" cho'qqisiga kengaytirishga harakat qiladi
• Va rang(v) = QORA va d(v) > d(u) ekanligini topadi.