32)Union Find algoritmi Ajıratılǵan jıynaq (Yamasa birlespe-tabıw )| 1-jıynaq (yo'naltirilmagan grafikda cikldı anıqlaw )Ajıratılǵan jıynaq maǵlıwmatlar strukturası - bul bir neshe ajıratılǵan (bir-birine uyqas kelmaytuǵın ) kishi jıynaqlarǵa bólingen elementler kompleksin gúzetip baratuǵın maǵlıwmatlar strukturası. Birlespeni tabıw algoritmı maǵlıwmatlar strukturasında eki paydalı operatsiyanı atqaratuǵın algoritm bolıp tabıladı:
Tabıw : Arnawlı bir element qaysı kishi jıynaqta ekenligin anıqlań. Bul eki element birdey kishi jıynaqta ekenligin anıqlaw ushın isletiliwi múmkin.
Birlespe: eki kishi jıynaqtı bir kishi jıynaqǵa birlestiring. Bul erda birinshi náwbette eki kishi jıynaq birdey jıynaqǵa tiyisli yamasa joq ekenligin tekseriwimiz kerek. Eger joq bolsa, biz birlespeni ámelge asıra almaymız.Bul postda biz Disjoint Set Data Structure qosımshasın talqılaw etemiz. Qosımsha berilgen grafikda cikl bar yamasa joq ekenligin tekseriw ushın mólsherlengen.
Yo'naltirilmagan grafikda cikl bar yamasa joq ekenligin tekseriw ushın Union-Find algoritmınan paydalanıw múmkin. Itibar beriń, biz cikldı anıqlaw algoritmın talqılaw etdik. Bul Union-Find-ga tiykarlanǵan taǵı bir usıl. Bul usıl grafikda óz-ózinen aylanıwlar joq ekenligin shama etedi.
Biz 1 D dızbektegi kishi jıynaqlardı baqlawımız múmkin, keling, onı ata-ana [] dep ataymız.
Keling, tómendegi grafiktı kórip shıǵayıq :
Hár bir shet ushın shettiń eki uchidan paydalanıp, kishi jıynaqlardı jaratıń. Eki shıń da birdey kishi jıynaqta bolsa, cikl tabıladı. Daslep, tiykarǵı dızbektiń barlıq slotlari -1 ge iske túsiriledi (hár bir kishi jıynaqta tek bir element bar ekenligin ańlatadı ).
33)Quick union find algoritmi Union Find Data Strukturası, 1-bólim: Tez tabıw algoritmı
Mashqala
Bul algoritmdıń maqseti eki elementtiń jalǵanǵanlıǵın anıqlaw bolıp tabıladı. Eger jalǵanbaǵan bolsa, olardı jalǵań. Bul mashqala dinamikalıq jalǵanıw mashqalası dep da ataladı. Bul baylanısıw ekvivalentlik munasábeti bolıp tabıladı. Biz sonday dep shama etemiz:
Simmetrik: Eger p q ga jalǵanǵan bolsa, q da p ga baylanısqan.
Transitiv: Eger p q ga hám q r ga jalǵanǵan bolsa, p r ga da jalǵanadı.
Refleksiv: p p menen baylanısadı. Tez tabıw algoritmınıń modeli:
Bul operativ tabıw algoritmı dinamikalıq jalǵanıw mashqalasın sheshiw ushın qızıǵıwshılıqlı algoritm dep ataladı. Maǵlıwmatlar strukturası N ólshem degi pútkil san dızbek identifikatorini óz ishine aladı. N hár qanday pútkil son bolıp tabıladı. Pútkil dızbek identifikatori [] 0 den N-1 aralıǵinda bolıwı kerek.p hám q id dızbekindegi 2 pútkil son bolıp tabıladı.p hám q birdey identifikatorga iye bolsa, jalǵanadı.
Men bul algoritmdı Java hám Python-de ámelge asıraman. Bul strukturanı rawajlandırıw ushın biz ámel etetuǵın qádemler bolıp tabıladı.
1-qádem:
Biz birinshi náwbette N kirgiziwdi beretuǵın konstruktordı islep shıǵıwımız kerek. N - joqarıda aytıp ótkenimdek, maǵlıwmatlar kólemi. Men konstruktor atınıń QuickFind retinde qo'yaman. Bul konstruktorda aldın N diapazonlı dızbekti jaratamız. Hár bir element 0 den baslanatuǵın element pozitsiyasi menen birdey bolǵan id bolıp tabıladı.
Mısalı, 1-poziciyanıń identifikatori 1, 0-poziciyanıń identifikatori 0, 7-pozitsiyasining identifikatori. 7 esaplanadı.
2-qádem:
Eki p hám q kiriwlerin alatuǵın “jalǵanıw” klasın islep shıǵıń. Bul olar qashannan berli jalǵanǵanlıǵın kórsetetuǵın logikalıq ma`nisin qaytaradı. Eger bul klass awa dep qaytarsa, algoritm hesh nárse etpeydi. Biraq eger ol joqtı qaytarsa, ol halda algoritm p hám q ni baylanıstıratuǵın birlespe operatsiyasın ámelge asıradı.
3-qádem:
p hám q ni baylanıstıratuǵın “union” atlı sinfni islep shıǵıń. Dızbek identifikatori arqalı tákirarlang. Qay jerde p dıń identifikatorini tapsańız, onı q dıń identifikatoriga ózgertiriń.
Birlespediń islewine mısal :
Mine biziń id dızbekimiz. Biz 0 den 8 ge shekem bolǵan diapazondı alamız.
0 1 2 3 4 5 6 7 8
Id 0 1 2 3 4 5 6 7 8
Birlespe (3, 4):
3 identifikatorini 4 identifikatoriga ózgertiriń.
0 1 2 3 4 5 6 7 8
Id 0 1 2 4 4 5 6 7 8
Birlespe (3, 8):
3 identifikatorini id 8 menen almastırıń. Joqarıdaǵı 3-basqıshda aytıp ótkenimdek, biz id dızbeki boylap tákirarlawımız kerek hám qay jerde 3 id identifikatoriga uqsas identifikatorni tapsak, onı id 8 ge ózgertiwimiz kerek.
0 1 2 3 4 5 6 7 8
Id 0 1 2 8 8 5 6 7 8
Birlespe (5, 6 ):
Bul birinshisi menen birdey boladı.
0 1 2 3 4 5 6 7 8
Id 0 1 2 8 8 6 6 7 8
Birlespe (4, 6 ):
0 1 2 3 4 5 6 7 8
Id 0 1 2 6 6 6 6 7 6
