Bog’langan componentlar (Connected components) esingizdami? Connected components deb, undirected graph‘dagi bir-biriga tog’ridan to’g’ri yoki oradagi vertex’lar orqali bog’langan komponentlar to’plamiga aytiladi.
Kuchli bog’langan komponentlar (strongly connected components, SCC) connected components’ning directed graph uchun mo’ljallangan ko’rinishi bo’lib, yagona farqi – strongly connected components’da vertex’lar ikki taraflama bog’langan bo’lishi kerak. Masalan, A dan B ga path bo’lsa, B dan A ga ham path mavjud bo’lishi zarur.
Graph’dagi SCClarni aniqlab olishdan maqsad, keyin ularni bir -biriga bog’langanini constant vaqt – O(1) ichida aniqlay olishdan iborat (huddi connected components kabi).
Kosaraju-Sharir algoritmi
Algoritm graph’dagi vertex’larni tekshirib chiqib, kuchli bog’langan vertex’larni id[] array ichida guruhlash uchun kerak. Har bir guruh uchun unikal son beriladi. id[] ni to’ldirib olganimizdan so’ng biz constant vaqt ichida ularni bog’langanligini tekshira olamiz. Agar id[v] == id[w] bo’lsa, demak ular bitta bog’lam ichida bo’ladi.
Kosaraju-Sharir algoritmining connected components‘dagi algoritmdan farqi – Kosaraju-Sharir algoritmida depth first search’dan ikki marta foydalaniladi (two pass).
Dastlab, graph’ni teskari o’girib, topological sortda bo’lgani kabi vertex’larning ketma-ketligi ro’yhatini topadi. Keyin shu ketma-ketlik bo’yicha original graph’da depth first search ichida guruhlab chiqadi.
Masalan bizda quyidagi graph bor bo’lsin.
Biz uni teskari o’giramiz:
Topological sortini topamiz: [ 1, 0, 2, 4, 5, 3, 11, 9, 12, 10, 6, 7, 8 ]
Topological sort tartibida depth first search’da guruhlab chiqamiz. Shunda graph’da 4ta strongly connected components borligi ma’lum bo’ladi.
Kod
Kod Githubda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/graphs/strongly-connected-components.js
* * *
Mavzu bo’yicha savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozishingiz yoki kodda Reference in new issue ni bosib, qoldirishingiz mumkin.