Չհատվող բազմության համակարգ

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search
Չհատվող բազմության համակարգ
Տեսակdata structure?
Դասtree data structure?
ԿազմելԲազմություն ստեղծում է 8 բազմություն։
Մի քանի Միացում գործողությունից հետո բազմությունները միանում են։

Համակարգչային գիտությունում չհատվող բազմության համակարգը տվյալների կառուցվածք է, որը իր մեջ պահում է մի խումբ էլեմենտներ, որոնք բաժանված են իրար հետ չհատվող ենթաբազմությունների։ Այն ապահովում է համարյա հաստատուն ժամանակ այնպիսի գործողությունների համար, ինչպիսիք են նոր բազմության ավելացումը, բազմությունների միացումը և բազմության որոշումը։ Այս տվյալների կառուցվածքը մեծ դեր է կատարում Կրուսկալի ալգորիթմում։

Պատմություն[խմբագրել | խմբագրել կոդը]

Չհատվող բազմության ցանցերը առաջին անգամ նկարագրվել են Ա․ Գալլերի և Մայքլ Ֆիշերի կողմից 1964-ին։ 1975-ին Ռոբերտ Տարյանը առաջինը ապացուցել է (Ակկերմանի հակադարձ ֆունկցիա) վատագույն դեպքի սահմանափակումը։

Ներկայացում[խմբագրել | խմբագրել կոդը]

Չհատվող բազմության անտառն ներառում է արժեքներ, որոնցից յուրաքանչյուրը ունի իր id-ին, ծնողի ցուցիչը և էֆեկտիվ ալգորիթմներում արժեք, որը պահում է իր կարգավիճակի համարը։

Էլեմենտների ծնող-ցուցիչները դասվորված են այնպես, որ կազմվի մեկ կամ մի քանի ծառ, յուրաքանչյուրը ներկայացվում է որպես բազմություն։ Եթե էլեմենտի ծնողի ցուցիչը հղում է դեպի իրեն, ապա այն ծառի արմատն է և այդ բազմության ներկայացուցիչը։ Բազմությունը կարող է ունենալ միայն մեկ էլեմենտ։ Եթե էլեմենտը ունի ծնող, ապա այն պատկանում է այն բազմության, որին պատկանում է իր ծնողը, և այդպես շարունակվում է մինչև արմատը։

Անտառները կարելի է ներկայացնել զանգվածների միջոցով, որտեղ ինդեքսները նրանց ծնողներն են։

Գործողություններ[խմբագրել | խմբագրել կոդը]

Կազմել բազմություն[խմբագրել | խմբագրել կոդը]

Այս գործողությունը ստեղծում է նոր բազմություն մեկ էլեմենտով, որը ունի իր id-ին, կարգավիճակը՝ 0 և ծնողի ցուցիչը դեպի իրեն։ Ծնողի ցուցիչը դեպի իրեն նշանակում է, որ նա իր բազմության ներկայացուցիչ է։

Այն իր աշխատանքի համար ծախսում է O(1) ժամանակ։

Փսեուդոկոդ:

Ֆունկցիա ՍտեղծելԲազմություն(x)

   եթե x գոյություն չունի:
     ավելացնել x չհատվող բազմության ծառին
     x.ծնող := x
     x.կարգավիճակ   := 0

Փնտրել[խմբագրել | խմբագրել կոդը]

Այս գործողությունը անցնում է ծնողների շղթայով մինչև հասնի այն էլեմենտին, որի ծնողը հենց ինքն է։

Ուղիների սեղմումը, այն դարձնում է ավելի արդյունավետ։ Մինչև արմատին հասնելը այն անցնում է ուրիշ գագաթներով, որոնք նույնպես պատկանում են այդ բազմությանը և սեղման ընթացքում այն վերահղվում է դեպի ծառի արմատը։ Վերջնական ծառը ավելի սեղմված է և արագացնում է հետագա գործողությունների ընթացքը։

Փսեուդոկոդ:

Ֆունկցիա Փնտրել(x)
   եթե x.ծնողը != x
     x.ծնողը := Փնտրել(x.ծնող)
   վերադարձնել x.ծնող

Միացում[խմբագրել | խմբագրել կոդը]

Միացում(x,y) օգտագործում է փնտրել ֆունկցիան x-ի և y-ի ծառերի արմատները գտնելու համար։ Եթե արամտները տարբեր են, ապա ծառերը միացվում են՝ վերահղելով մեկի արմատը մյուսին։ Եթե այն կատարվի հասարակ տարբերակով, օրինակ միշտ սարքելով x-ը y-ի երեխան, ծառի երկարությունը կարող է հասնել մինչև ։ Այն շրջանցելու համար օգտագործվում է միացում ըստ կարգավիճակի։

Միացումը ըստ կարգավիճակի միշտ վերահղում է ցածր ծառը դեպի բարձր ծառի։

Այս իմպլեմենտացիան իրագործելու համար յուրաքանչյուր էլեմենտին տրվում է կարգավիճակ։ Սկզբում բազմությունն ունի մեկ էլեմենտ և կարգավիճակը՝ զրո։ Եթե երկու բազմություն միացել են և ունեն նույն կարգավիճակը, ապա վերջնական բազմության կարգավիճակը մեկով մեծանում է, հակառակ դեպքում մեծ կարգավիճակը վերագրվում է վերջնական բազմության կարգավիճակին։

Փսեուդոկոդ:

 ֆունկցիա Միացում(x, y)
   xԱրմատ := Փնտրել(x)
   yԱրմատ := Փնտրել(y)
 
   // x և y նույն բազմությունում են
   if xԱրմատ == yԱրմատ            
       վերադարձնել
   
   // x և y նույն բազմությունում չեն
   եթե xԱրմատ.կարգավիճակ < yԱրմատ.կարգավիճակ
     xԱրմատ.ծնող := yԱրմատ
   հակառակ եթե xԱրմատ.կարգավիճակ > yԱրմատ.կարգավիճակ
     yԱրմատ.ծնող := xԱրմատ
   հակառակ
     //Պատահականորեն ընտրել մեկին, որպես ծնող
     yԱրմատ.ծնող := xԱրմատ   
     xԱրմատ.կարգավիճակ   := xԱրմատ.կարգավիճակ + 1