Chuqurlik bo‘yicha qidiruv (DFS)

Chuqurlik bo‘yicha qidiruv (DFS)ni o‘rganing

Kirish

Chuqurlik bo‘yicha qidiruv (DFS) — graflar bilan ishlash uchun asosiy algoritmlardan biri.

DFSning asosiy g‘oyasi — joriy cho‘qqidan imkon qadar chuqurroq borish va faqat tashrif buyurilmagan qo‘shni cho‘qqilar qolmaganda qaytishdir.

U qanday ishlaydi?

Biz bitta cho‘qqidan boshlaymiz. Uni ziyorat qilgandan so‘ng, hali ziyorat qilinmagan har bir qo‘shni cho‘qqi uchun DFSni rekursiv tarzda ishga tushiramiz. Shu tariqa, boshlang‘ich cho‘qqidan yetib borish mumkin bo‘lgan barcha cho‘qqilarni ziyorat qilamiz.

Graf Qirralarining Tasnifi

DFSni ishga tushirganda, qirralarni ularning uchlarining kirish va chiqish vaqtlaridan foydalanib tasniflash mumkin.

Bu tasnif ko‘pincha graf masalalarida foydali bo‘ladi.

Faraz qilaylik, DFS $(x, y)$ qirrani qayta ishlayapti.

1. Agar $y$ cho‘qqi hali ziyorat qilinmagan bo‘lsa

• Daraxt qirrasi — agar DFS $y$ ni birinchi marta ziyorat qilish uchun $(x, y)$ orqali o‘tsa, bu qirra daraxt qirrasi deb ataladi.