Depth first search (DFS) algoritmi oson klassik graph algoritmlaridan biri bo’lib, u rekursiya ichida graph’dagi barcha vertex’larni tekshirib chiqishga yordam beradi. Aslida biz bu algoritmdan binary search tree‘dagi barcha ma’lumotlarni ko’rib chiqish uchun foydalanib, traverse() funksiyasini yozganmiz.
Depth first search algoritmining klassik deyilishiga sabab, qadimda undan labirintdan chiqish yo’lini topish uchun foydalanishgan. Labirintning boshlanish joyida g’altak – koptok qilib o’ralgan ipni ochib, yo’lni topishga kirishishgan. Berk ko’chaga kirib qolishganda, ip bo’yicha orqaga qaytib, kirilmagan yo’ldan davom ettirishgan. Shu tariqa ip orqali yurilgan yo’llarga qayta kirmaslik uchun ularni belgilab borishgan. Ip orqali yo’l topishni Trémaux maze exploration deb ham ataladi.
Labirint yechishni dasturda modellashtirish uchun labirintni graph’ga aylantiramiz. Bunda labirintning yo’llari edge’lar, chorrahalar vertex’lar bo’ladi.
Avvaldan aytib o’tish kerakki, Depth first search algoritmi labirintdan tez chiqib ketish uchun eng yaxshi yechim emas, u qisqa yo’lni topmaydi. Algoritm shunchaki «boshi oqqan ko’chaga» kirib chiqib, yo’l bor yo’qligini tekshiradi.
Kompyuterchasiga tushuntirganda, vertex’ning edge’lari bor yo’qligini tekshiradi, bor bo’lsa, har bir edge’dagi vertex’dan tekshiruvni davom ettiradi.
Algoritmning ishlash tartibi (vizualizatsiya)
Quyidagi graphning barcha vertex’larini tekshirib, qiymatlarini yig’ib chiqishimiz kerak bo’lsin.
DFS algoritmini A vertex’dan boshlaymiz. A topildi, uni «o’qilgan» qilib belgilaymiz (marked). Rekursiv funksiya stack tartibida ishlagani uchun, stack’ning tepasida A turipti, ya’ni funksiya A vertex uchun ishlamoqda.
A vertex bog’langan boshqa vertex’larni tekshiramiz. U B va G ga ulangan. Tekshiruvni B dan davom ettiramiz. Nima uchun B’dan? Aslida DFS algoritmi uchun B yoki G dan davom ettirishning ahamiyati yo’q. Esingizda bo’lsa graph uchun api yozganimizda, biz edge’larni Set ichida saqlagandik. Edge’ni o’qib olishda ham Set beradigan edge’lar bo’yicha DFS ishni davom ettiradi.
B stack’ning yuqorisida. Algoritm B’ga bog’langan tekshirilmagan vertex’larini tekshiradi. Ular C va G. C dan davom ettiradi.
C ga bog’langan tekshirilmagan vertex’lari yo’q. Stack’dagi C funksiya ishini to’xtatadi, demak C stackdan o’chiriladi.
Endi stack’ning yuqorisida B turipti. B ga bog’langan kirilmagan vertex – G.
G stack’ga qo’shiladi.
G stack’ning yuqorisida. G ga bog’langan kirilmagan bitta vertex bor – E.
E da kirilmagan ikki vertex bor: J va K. J dan davom ettiradi.
J ning kirilmagan ikki vertex bor: F va D. D dan davom ettiradi.
D ning kirilmagan bitta vertex bor: K. K dan davom ettiradi.
K ga bog’langan kirilmagan vertex yo’q. K stackdan chiqariladi – rekursiyadagi K funksiya ishini tugatadi.
D ga bog’langan kirilmagan vertex yo’q. D stackdan chiqariladi – rekursiyadagi D funksiya ishini tugatadi.
J stack’ning yuqorisida. J ga bog’langan kirilmagan F vertex bor. F dan davom ettiradi.
F ga bog’langan kirilmagan vertex’lar yo’q. F stackdan chiqariladi – rekursiyadagi F funksiya ishini tugatadi.
J ga bog’lagan kirilmagan vertex’lar yo’q. J stackdan chiqariladi.
E ga bog’langan kirilmagan vertex’lar yo’q. E stackdan chiqariladi.
G ga bog’langan kirilmagan vertex’lar yo’q. G stackdan chiqariladi.
B ga bog’langan kirilmagan vertex’lar yo’q. B stackdan chiqariladi.
A ga bog’langan kirilmagan vertex’lar yo’q. A stackdan chiqariladi.
DFS algoritmi ishini tugatdi.
Depth first search algoritmini kodda ifodalash
Graph yasash uchun bizda allaqachon Graph API bor. Kirilgan vertex’larni marked[] da belgilab, edgeTo[] ga esa vertex’ga qaysi vertex’dan kelinganini qo’shib boramiz. Shunda edgeTo[w] == v degani, w vertex’ga v vertex’dan kelinganini bildiradi. edgeTo dagi ma’lumotlar asosida biz bir vertex’dan ikkinchi vertex’ga yo’lni topishimiz mumkin.
Quyidagi funksiya deep first search algoritmi asosida berilgan vertex’ga bevosita va bilvosita bog’langan vertex’lar ro’yhatini qaytaradi:
Ikki vertex orasidagi yo’lni topish Graph APIda realizatsiya qilingan:
https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/graphs/adjacency-list-graph.js
* * *
Manbalar
Depth-First Search
https://www.coursera.org/learn/algorithms-part2/lecture/mW9aG/depth-first-search
Depth First Search (DFS) Algorithm Visually Explained
https://levelup.gitconnected.com/depth-first-search-dfs-algorithm-visually-explained-87bca008085f