WALKER

Dasturchi, frilanser, gik va introvert

by Sherzod Shermukhamedov

Dinamik boğlaniş (Dynamic Connectivity), Union-Find

Dinamik boğlaniş (Dynamic Connectivity), Union-Find

Kompyuter va graph nazariyasida dinamik boğlaniş deb boğlangan komponentlar örtasidagi ma'lumotlarni özida saqlaydigan ma'lumotlar tuzilmasiga aytiladi. Dinamik boğlanişga ega sodda ma'lumot tuzilmasiga Disjoint-set (yoki union-find) ni misol qilib keltiriş mumkin.

Union-find tuşunarli bölişi uçun real-hayotdan misol keltiraman. Yomğir vaqtida derazadagi suv tomçilarini tasavvur qiling. Ikki tomçi bir biriga yaqin kelganda qaysidir muddatda ular birlaşib bitta tomçiga aylanib qoladi. Mana şu birlaşiş union-find'dagi union qismi.

Dasturlaşdagi misol. Bizda juda köp node'lar bor va ularning ba'zilari ba'zilari bilan guruhlangan:

Ikki node'ning bir guruhda ekanligini aniqlaş uçun "sariq va qora node'lar bir guruhdami?" deb söraymiz. Yuqoridagi rasmga köra sariq va qora node ikkisi qizil node'ga boğlangan. Demakki ular orasida boğlaniş bor, ular bir guruhda.

Endi ikki guruh örtasida union amalini bajaramiz:

E'tiborga molik jihati, union-find strukturasida ulanişni orqaga qaytarişning, ulangan qismni qayta ajratişning imkoni yöq.

Bazaviy tuşunçaga ega böldik, endi qanday qilib union-find algoritmini amalga oşiramiz?

Bizda quyidagiça node guruhlari bor:

Har bir node özida boşqa node'ga körsatkiçni (pointer) saqlaydi. Har bir komponentdagi (guruhdagi) bitta node'da pointer bölmaydi. Ana öşa node komponentning özagi (root) deb ataladi. Bizning misolda root'lar - qizil, kök va puşti node'lar.

Ikki komponentni birlaştiriş uçun yana bir pointer qöşamiz:

Natijada kök node kattalaşgan komponentning özagi (root), qizil node esa endi root emas.

Yuqorida aytib ötganimizdek, union-find data structure'ning mazmuni ikki node bir komponent içida ekanligini aniqlay olişimizda. Buning uçun topiş (find) amali - node'larni tekşirib ularning pointeri böyiça root'ni qaytariş. Misolimizda biz sariq node'ning root'ini topmoqçi bölsak, sariq -> qizil -> kök ga kelamiz. Yaşilni tekşirib ham biz kökga yetib boramiz. Demak sariq va yaşil bitta root'da birlaşgani uçun uşbu ikki node bitta komponent içida böladi.

Strukturada node'lar köp bölganda pointerlar orqali topiş qiyin effektiv bölmasligi mumkin çunki bunda node'ning root'gaça bölgan yöli uzun bölişi mumkin. Union-find qanday yeçim beradi? Ikki optimizatsiya:

  • Path compression. Biz find amalini bajarganimizda pointerlar orqali topib kelamiz. Aslida union-find uçun yölning uzunligi muhim emas. Şuning uçun biz node'ni töğridan töğri root'ga ulab qöyişimiz ham mumkin. Buni yölni qisqartiriş (path compression) deyiladi. Qança köp yöl qisqartirsak, node'ni tekşiriş şunça tezlaşadi.

  • Merge by rank (Darajasi böyiça birlaştiriş). Daraxt kabi bir neça darajaga ega ikki komponentni birlaştirganimizda, qisqaroq daraxtni uzunroq daraxtga birlaştirişimiz mumkin. Buning uçun komponentlarning uzunligini saqlaşimiz kerak böladi, ammo bu qiyin iş emas.

Dasturlaş

Dasturlaşda union-find structure uçun array'dan foydalaniladi.

Quyida biz bir neça yöllarni körib çiqamiz.

Eager approaç (Quick-Find)

Data structure: N uzunlikdagi array id[]
Natija: p va q da bir xil id bölsa, ular boğlangan böladi.

Find. p va q bir xil id ga ega ekanligini tekşiriş
Union. p va q joylaşgan komponentlarni birlaştiriş uçun id'si id[p] va id[q] ga teng bölgan node'larni özgartiriş.

Yaxşiroq tuşuniş uçun kodni özingiz debug qilib körişingiz mumkin.

Eager approaç'ning kamçiligi:
Algoritm quadratic time - O(n^2), çunki n uzunlikdagi array elementlarining barçasini boğlab çiqiş uçun n^2 vaqt ketadi. find() esa constant time. find() constant time bölgani kompensatsiyasini union() da tölaymiz. Kvadratik algoritmlar esa katta hajmdagi ma'lumotlar uçun sekin işlaydi.

Lazy approaç (Quick-Union)

Lazy approaç'da p va q node'larni boğlaş uçun p'ning root'iga q'ning root'ini beramiz. Tekşirişda esa p va q node'larning root'i bir-biriga tengligini, ya'ni bir root'da ekanligini aniqlaymiz.

Lazy approaç ham sekin algoritm, sababi find() da ikki node'ning root'ini topişimiz uçun root'gaça bölgan elementlarni tekşirib çiqişimiz kerak. Qöşimçasiga, union() da boğlanişlar uzun bölib ketişi mumkin.

Weighted quick-union

Yuqoridagi quick-union'ni uzun boğlamlar hosil bölmasligi uçun optimallaştiramiz. Buning uçun har bir boğlamning uzunligini (boğlamdagi node'larning sonini) alohida array'da yiğib boramiz. Ikki boğlamni qöşganda esa kiçikroq boğlam root'ini kattaroq boğlamning root'iga boğlaymiz.

Yana optimallaştiriş mumkinmi? Mumkin, uzun boğlamlardagi node'larni rootga boğlaş orqali. Buni path compression deyiladi.

Kodlarni Githubda ham körib çiqişingiz mumkin: https://github.com/Webmaxor/leetcode-solutions/tree/master/algorithms/union-find

Savollarni githubda yangi tema (New issue) oçib yozib qoldiring: https://github.com/Webmaxor/leetcode-solutions/issues

Xulosa

Uzun maqolada Union-Find'ni aniq, tuşunarli yozdim deb öylamayman. Menimça kodni işlatib, debug qilib körganda, algoritm işlaşini köproq tuşuniş mumkin böladi.


Mavzu böyiça savollarni Github'dagi Webmaxor / leetcode-solutions repository'da yozişingiz yoki kodda **Reference in new issue **ni bosib, qoldirişingiz mumkin.