გაერთიანება-ძებნა (DSU)

მეგობრების ჯგუფები ერთიანდება, კაბელები კომპიუტერებს აკავშირებს, პიქსელები უბნებად ერთიანდება. Union-Find პასუხობს კითხვას „ეს ორი ერთ ჯგუფშია?“, მაშინაც კი, როცა ჯგუფები განუწყვეტლივ ერთიანდება, თითქმის მუდმივ დროში. ის კრასკალის ალგორითმის ძრავაცაა.

საშუალო⏱ 12 წთ

←ეყრდნობა

5ხეები: ცნებები, თვისებები, შემოვლებიDSU-ს ყოველი ჯგუფი ხეა, find კი მის სათავემდე ადის.6სიღრმეში ძებნა (DFS)DSU პასუხობს „ბმულია?“ როგორც DFS კომპონენტებზე, მაგრამ სწრაფი რჩება, როცა წიბოები ემატება.

გზას უხსნის→

8მინიმალური დამფარავი ხე: კრასკალი და პრიმიკრასკალი ყოველ წიბოზე კითხულობს „ერთ კომპონენტშია?“, ეს კი DSU-ს find-ია.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01ორი ოპერაცია: find და union

არაგადამკვეთი სიმრავლეების გაერთიანება (DSU, Union-Find) ელემენტებს ჯგუფებად ყოფს, რომლებიც ერთმანეთს არ ეფარება. მას მხოლოდ ორი ოპერაცია აქვს:

find(x): რომელ ჯგუფშია x? აბრუნებს წარმომადგენელს, ამიტომ find(a) == find(b) ნიშნავს „ერთ ჯგუფშია“.
union(a, b): a-სა და b-ს ჯგუფების გაერთიანება.

შეიძლებოდა ყოველი გაერთიანებისას ყველა წევრისთვის ჭდე გადაგვეწერა, მაგრამ ორი დიდი ჯგუფის გაერთიანება მაშინ O(n) დაჯდებოდა. ყოველ კითხვაზე გრაფში ძებნა კიდევ უარესია. DSU ორივე ოპერაციას თითქმის O(1)-ში ასრულებს, ოღონდ ჯგუფის ხელახლა გაყოფა არ შეუძლია (ეს არის ფასი).

ტიპური გამოყენება: ბმული კომპონენტები, როცა წიბოები თანდათან ემატება; ციკლის აღმოჩენა წიბოს დამატებისას; და კრასკალის მინიმალური დამფარავი ხე, შემდეგი თემა.

02მშობლის მიმთითებლების ტყე

ვინახავთ ერთ მასივს, parent[]. ყოველი ჯგუფი ხეა, ყოველი ელემენტი თავის მშობელზე მიუთითებს, სათავე კი საკუთარ თავზე მიუთითებს და ჯგუფს ასახელებს. თავიდან parent[i] = i: ყოველი ელემენტი თავისი ერთელემენტიანი ხეა.

find(x): მივყვეთ parent-ს, ვიდრე parent[r] == r, დავაბრუნოთ r.
union(a, b): ვიპოვოთ ორივე სათავე; თუ განსხვავდება, ერთი მეორის მშობლად ვაქციოთ.

ეს არის მთელი სტრუქტურა: რამდენიმე სტრიქონი და ერთი მასივი. სურათზე find(4) გადის 4 → 3 → 1 და პასუხობს 1-ს, ამიტომ 4 და 2 ერთ ჯგუფშია, 6 კი (სათავე 5) არა.

ერთადერთი საფრთხე ხეების ფორმაა: find იმდენი ჯდება, რამდენიც ელემენტის სიღრმეა.

03დაბალი ხეები: რანგით გაერთიანება

თუ union პირველ სათავეს ყოველთვის მეორის ქვეშ კიდებს, გაერთიანებების ცუდი რიგი ჯაჭვს აგებს და find ძირში O(n) ჯდება.

რანგით გაერთიანება ამას ასწორებს: ყოველი სათავისთვის ვინახავთ rank[]-ს (ხის სიმაღლის ზედა ზღვარს) და ყოველთვის დაბალ ხეს მაღლის ქვეშ ვაბამთ. მხოლოდ ტოლი რანგებისას იზრდება ახალი სათავის რანგი 1-ით. r რანგის ხეში მაშინ მინიმუმ 2ʳ ელემენტია, ამიტომ სიმაღლე O(log n) რჩება.

ზომით გაერთიანება (პატარა ჯგუფი დიდის ქვეშ) იმავე გარანტიას იძლევა და ისეთივე გავრცელებულია; აირჩიე ნებისმიერი.

04გზის შეკუმშვა და თითქმის მუდმივი შეფასება

მეორე ხრიკი: როცა find(x) სათავემდე ავიდა, ამ გზის ყველა წვერო პირდაპირ სათავეზე მივმართოთ. მათგან შემდეგი find ერთ ნაბიჯს დასჭირდება. კოდში ეს ერთი სტრიქონია:

int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }

ვიზუალიზატორის გაშვებაში find(8) გადის 8 → 7 → 5 → 1, ამის შემდეგ კი 8, 7 და 5 სამივე 1-ზე მიუთითებს.

ორივე ხრიკით m ოპერაციის ნებისმიერი მიმდევრობა O(m · α(n)) ჯდება, სადაც α აკერმანის შებრუნებული ფუნქციაა: ნებისმიერი რეალური n-ისთვის ის 4-ს არ აღემატება. პრაქტიკაში ეს ოპერაციაზე მუდმივი დროა.

ფასი ერთი შეხედვით

find / union (რანგი + შეკუმშვა)O(α(n)) amortized

მხოლოდ რანგით გაერთიანებაO(log n)

ოპტიმიზაციების გარეშე (უარესი)O(n)

მეხსიერებაO(n)

დაიმახსოვრე

DSU ყოველ ჯგუფს parent[] მასივში ხის სახით ინახავს; სათავე ჯგუფის სახელია.
რანგით გაერთიანება ხეებს დაბალს ინახავს, გზის შეკუმშვა კი ძებნისას აბრტყელებს.
ერთად ისინი find-სა და union-ს პრაქტიკულად O(1)-ად აქცევს, და სწორედ ეს სჭირდება კრასკალს.

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: უყურე rank სტრიქონს: ის მხოლოდ ტოლი რანგის სათავეების გაერთიანებისას იზრდება. ბოლოს ნახე, როგორ აბრტყელებს find(8) თავის გზას.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

არაგადამკვეთი სიმრავლეები (DSU)

i	1	2	3	4	5	6	7	8
parent[]	1	2	3	4	5	6	7	8
rank[]	0	0	0	0	0	0	0	0

Union-Find ელემენტებს არაგადამკვეთ სიმრავლეებად ყოფს და ტყის სახით ინახავს: ყოველი სიმრავლე ხეა, მისი სათავე კი სიმრავლის „სახელია“. თავიდან ყოველი ელემენტი თავისივე სათავეა.

ფსევდოკოდი

 1 each element starts as its own set (parent[i] = i) 2 find(x): follow parent[] up to the root 3 union(a,b): link the root of one under the other 4   attach the smaller-rank root under the larger  (union by rank) 5   equal ranks → pick one, its rank grows by 1 6 find(x) also flattens the path (path compression): 7   point every node on the path directly at the root

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

თავიდან 1…4 ცალ-ცალკეა. შევასრულოთ union(1,2), union(3,4), union(1,3) რანგით; ტოლი რანგებისას პირველი არგუმენტის სათავე ხდება მშობელი. რომელია 4-ის სათავე?

№2

რას ცვლის გზის შეკუმშვა?

№3

გრაფს ვუმატებთ წიბოს (u, v): როდის ქმნის ის ციკლს?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

LeetCodeNumber of Provinces საშუალო↗LeetCodeRedundant Connection საშუალო↗CSESRoad Construction საშუალო↗LeetCodeAccounts Merge საშუალო↗