Graph’da bog’langan komponentlar

Bog’langan komponentlar (Connected components, CC) deb graph‘dagi bir-biriga tog’ridan to’g’ri yoki oradagi vertex’lar orqali bog’langan komponentlar to’plamiga aytiladi. Amaliyotda agar ikki vertex orasida path bo’lsa, biz ularni bog’langan deb ayta olamiz.

Connected components haqida biz Union-Find ma’lumot tuzilmasida tanishib o’tgan edik. Ushbu mavzudan maqsad esa, connected components’ni constant vaqt – O(1) ichida aniqlay olishni ko’rib chiqishdan iborat.

Bog’lanish uch xil turda bo’ladi:

• Reflexive: v o’ziga o’zi bog’langan – ichki bog’lanish.
• Symmetric: agar v vertex w ga bog’langan bo’lsa, demak w ham v ga bog’langan – undirected graph’dagi vertex’larga xos.
• Transitive: agar v w‘ga bog’langan bo’lsa va w x‘ga bog’langan bo’lsa, demak v x‘ga bog’langan.

Vertex’lar bog’langanligini tekshirishdan avval ularni depth first search yordamida tekshirib, komponentlarni id[] array ichida guruhlab olamiz. Bitta bog’lamdagi komponentlar uchun bitta id beramiz.

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.

Kod

Biz connected components’ni adjacency list‘ga aralashtirmaslik va kodni sodda saqlab qolish uchun alohida API yozamiz. APIning dastlabki qiladigan ishi – graph’dagi vertex’larni depth first search yordamida o’qib olib, component ID larini (this.id) to’ldirishdan iborat. Keyin biz ID lar bo’yicha vertex’larni bog’langan-bog’lanmaganligini tekshiramiz.

Kod Githubda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/graphs/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.