Graph’dagi aylanalarni topish

Graph’da aylana (cycle) nimaligi haqida graph atamalarida tushuntirilgan.
Bir graph’da aylanalar bir nechta bo’lishi mumkin.

Ularni topish uchun har doimgidek depth first search‘dan foydalanamiz.

Ishlash tartibi

• Biz aylana qayerdan boshlanishini bilmaganimiz uchun, graph’ning har bir elementini aylananing boshi sifatida ko’rib chiqamiz.
• Depth first search’da edge’lari bo’yicha tekshiruvni davom ettiramiz. Bunda ko’rilgan vertex’larni marked o’zgaruvchiga yig’ib boramiz. Bog’langan vertex’larni path o’zgaruvchisiga yig’amiz.
• Agar path’dagi vertex’lar soni 2 dan oshsa, demak aylana bo’lishi mumkin. Path’ning ohirgi vertex’ining edge’larida path’ning birinchi vertex’i bor bo’lsa, demak aylana topilgan bo’ladi. Aylanalarni cycles o’zgaruvchiga yig’amiz.
• Biz graph’ning har bir elementini ko’rib chiqqanimiz bois, bir xil aylanalar turlicha vertex ketma-ketligida keladi. Masalan bitta aylana 0 – 1 – 5 – 4, 1 – 0 – 4 – 5, 4 – 0 – 1 – 5, 5 – 1 – 0 – 4 ketma-ketligida uchraydi. Bizga ketma-ketlikning ahamiyati yo’q, shu sababli faqat bittasini cycles o’zgaruvchiga olamiz. Qaytarilishlarning oldini olish uchun path’larni dictionary ko’rinishida saqlaymiz.

Kod

Note: graphda ierarxik aylanalar bo’lganda, funksiya ularning hammasini topmaydi. Masalan quyidagi graph’da 6 ta aylana bor. Funksiya ulardan faqat 4tasini topdi.

Graph’da aylanalarni topish Leetcode masalalarida turlicha ko’rinishda uchraydi. Masalalarda aynan graph’ni eslatib o’tilmasada, masalaning berilishiga qarab, graph’ni qo’llashni aniqlay olish zarur bo’ladi.

Misol uchun 207. Course Schedule masalasini yechish uchun berilgan qiymatlar asosida graph aylanami yoki yo’qmi – aniqlash kerak.