Vaqt murakkabligi
O(V + E)
DFS — grafni aylanib chiqish algoritmi bo'lib, orqaga qaytishdan oldin har bir tarmoq bo'ylab imkon qadar chuqurroq borib o'rganadi. U stek yoki rekursiyadan foydalanadi.
Qanday ishlaydi:
1. Boshlang'ich tugundan boshlash va uni tashrif buyurilgan deb belgilash
2. Tashrif buyurilmagan har bir qo'shni tugunga rekursiv o'tish
3. Tashrif buyurilmagan qo'shni tugunlar qolmaganda orqaga qaytish
4. Barcha erishish mumkin bo'lgan tugunlar ko'rib chiqilguncha davom etish
Vaqt murakkabligi: O(V + E)
V = tugunlar soni, E = qirralar soni
Xotira murakkabligi: O(V) — rekursiya steki va tashrif buyurilgan tugunlar to'plami uchun
Qo'llanilish sohalari:
- Grafdagi sikllarni aniqlash
- Topologik saralash
- Bog'langan komponentlarni topish
- Labirint va boshqotirmalarni yechish
- Yo'llarni qidirish
DFS avval eng chuqur yo'llarni o'rganadi. Shu sababli u topologik saralash va sikllarni aniqlashda foydali, ammo eng qisqa yo'lni topishni kafolatlamaydi.
O'xshash algoritmlar
Ko'p beriladigan savollar
- Chuqurlik bo'yicha qidiruv (Depth-First Search, DFS) nima?
- DFS — grafni aylanib chiqish algoritmi bo'lib, orqaga qaytishdan oldin har bir tarmoq bo'ylab imkon qadar chuqurroq borib o'rganadi. U stek yoki rekursiyadan foydalanadi.
- Chuqurlik bo'yicha qidiruv (Depth-First Search, DFS) murakkabligi qanday?
- Vaqt (o'rtacha): O(V + E) · Xotira: O(V)
- Ushbu Chuqurlik bo'yicha qidiruv (Depth-First Search, DFS) vizualizatori kimlar uchun?
- Chuqurlik bo'yicha qidiruv (Depth-First Search, DFS) vizualizatsiyasi "Graflar" kategoriyasida o'rta darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
- Chuqurlik bo'yicha qidiruv (Depth-First Search, DFS) ga o'xshash qanday algoritmlar bor?
- Shu kategoriyada (Graflar) quyidagilarni ko'rishingiz mumkin: Breadth-First Search, Dijkstra's Algorithm, Prim's Algorithm. Har biri interaktiv vizualizatsiyaga ega.