Algo Visualizedდაიწყე სწავლა

მინიმალური დამფარავი ხე: კრასკალი და პრიმი

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

მოწინავე⏱ 14 წთ

←ეყრდნობა

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

გზას უხსნის→

12P და NP, ალგორითმის არჩევამინიმალური დამფარავი ხე მეტრიკულ კომივოიაჟერს ოპტიმუმზე მაქსიმუმ ორჯერ გრძელ მარშრუტს აძლევს: სირთულესთან გამკლავების კლასიკური გზა.
1ისწავლე2ითამაშე3შეამოწმე4ივარჯიშე
01

ისწავლე

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

01დამფარავი ხე, მინიმალური ჯამური წონა

ავიღოთ ბმული, არაორიენტირებული, წონადი გრაფი. დამფარავი ხე წიბოების ისეთი სიმრავლეა, რომელიც ყველა V წვეროს აკავშირებს და ციკლს არ შეიცავს; მასში ყოველთვის ზუსტად V − 1 წიბოა. მინიმალური დამფარავი ხე (MST) ისეთია, რომლის ჯამური წონა უმცირესია.

შეადარე უმოკლეს გზებს: MST ამცირებს ყველა არჩეული წიბოს ჯამს და არა მანძილს ერთი წვეროდან. MST-ში ორ წვეროს შორის გზა შეიძლება გრძელი იყოს; იაფია ქსელი მთლიანად.

ვიზუალიზატორის 7-წვეროიან გრაფში MST 6 წიბოს იყენებს და მისი ჯამური წონაა 39. როცა წონები მეორდება, შეიძლება რამდენიმე MST არსებობდეს, მაგრამ მინიმალური ჯამი ერთადერთია.

758975156891112345677 წვერო → 6 წიბოციკლის გარეშეჯამური წონა 39

02რატომ მუშაობს აქ ხარბი: ჭრილის თვისება

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

დამტკიცება გაცვლის არგუმენტია, ზუსტად როგორც აქტივობების არჩევაში (ეტაპი 7). ავიღოთ MST, რომელშიც ეს წიბო e არ არის. e-ს დამატება ციკლს ქმნის, ეს ციკლი კი ჭრილს მეორედაც უნდა კვეთდეს რომელიღაც f წიბოთი. რადგან w(e) ≤ w(f), f-ის e-ით ჩანაცვლება გვაძლევს დამფარავ ხეს, რომელიც არ არის უფრო მძიმე.

ე.ი. ჭრილის გადამკვეთი უმსუბუქესი წიბოს დამატება ყოველთვის უსაფრთხოა. ორივე კლასიკური ალგორითმი უბრალოდ ორი სხვადასხვა ხერხია, რომელ ჭრილს შევხედოთ.

ერთი მხარემეორე მხარე75897515689111234567ჭრილის უმსუბუქესი წიბო უსაფრთხოა

03კრასკალი: დაალაგე წიბოები, ციკლები DSU-ით გამოტოვე

კრასკალის ალგორითმი წიბოებს უმსუბუქესიდან უმძიმესისკენ განიხილავს:

  • ყველა წიბო დავალაგოთ წონით;
  • ყოველი წიბოსთვის (u, v): თუ find(u) != find(v), ავიღოთ და union(u, v); წინააღმდეგ შემთხვევაში ციკლს შექმნიდა, გამოვტოვოთ;
  • გავჩერდეთ V − 1 წიბოს შემდეგ.

ყოველი მიღებული წიბო უმსუბუქესია ჭრილზე „u-ს კომპონენტი და დანარჩენი“, ამიტომ ჭრილის თვისება მას უსაფრთხოს ხდის. ციკლის კითხვას წინა თემის DSU თითქმის O(1)-ში პასუხობს.

ჩვენს გრაფზე: 1-4 (5) ✓, 3-5 (5) ✓, 4-6 (6) ✓, 1-2 (7) ✓, 2-5 (7) ✓, მერე 2-3, 5-6 და 2-4 გამოიტოვება, 5-7 (9) კი ხეს ასრულებს: 39. სულ O(E log E), რასაც სორტირება განსაზღვრავს.

კრასკალი: წიბოები წონის ზრდით1-4(5)✓3-5(5)✓4-6(6)✓1-2(7)✓2-5(7)✓2-3(8)✗5-6(8)✗2-4(9)✗5-7(9)✓6-7(11)4-5(15)✓ სხვადასხვა კომპონენტი → ვიღებთ✗ find(u) == find(v) → ციკლი, გამოვტოვებთ5 + 5 + 6 + 7 + 7 + 9 = 39

04პრიმი: დეიქსტრა სხვა გასაღებით

პრიმის ალგორითმი ერთ ხეს ზრდის საწყისი წვეროდან. ყოველ ნაბიჯზე უმატებს უმსუბუქეს წიბოს, რომელიც ხიდან გარეთ მყოფ წვეროზე მიდის: ჭრილია „ხე და დანარჩენი“.

კოდში ეს თითქმის სტრიქონ-სტრიქონ დეიქსტრაა: მინ-გროვა, ამოიღე უმცირესი, მონიშნე, განაახლე მეზობლები, გამოტოვე მოძველებული წყვილები. ერთადერთი განსხვავება გასაღებია:

  • დეიქსტრა: d[v] = d[u] + w, მთელი მანძილი საწყისიდან;
  • პრიმი: key[v] = w, მხოლოდ ის ერთი წიბო, რომელიც v-ს ხეს მიაბამს.

ორობითი გროვით პრიმი O(E log V) ჯდება. კრასკალი უფრო მარტივია, როცა წიბოების სია უკვე გაქვს; პრიმი მკვრივ გრაფებს და მოსაზღვრე წვეროთა სიებს უხდება. ორივე აქ 39-ს პოულობს, ნებისმიერი საწყისი წვეროდან.

დეიქსტრაpop (k, u) with min kmark ufor edge (u, v, w): if d[u] + w < d[v]: d[v] = d[u] + w push, p[v] = uპრიმიpop (k, u) with min kmark ufor edge (u, v, w): if w < key[v]: key[v] = w push, p[v] = uიგივე ჩონჩხი: მინ-გროვა, ამოიღე მინიმუმი, მონიშნე, განაახლე მეზობლები

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

კრასკალი (სორტირება + DSU)O(E log E)
პრიმი ორობითი გროვითO(E log V)
პრიმი მკვრივ გრაფზე, მასივითO(V²)

დაიმახსოვრე

  1. მინიმალური დამფარავი ხე ყველა V წვეროს V − 1 წიბოთი აკავშირებს უმცირესი ჯამური წონით.
  2. ჭრილის თვისება ხარბს უსაფრთხოს ხდის: ნებისმიერი ჭრილის უმსუბუქესი გადამკვეთი წიბო რომელიღაც MST-ს ეკუთვნის.
  3. კრასკალი = დალაგებული წიბოები + DSU-ით ციკლის შემოწმება; პრიმი = დეიქსტრა, რომლის გასაღები ერთი წიბოს წონაა.
02

ითამაშე

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

👀 რას უყურო: კრასკალის ფაზაში დააკვირდი უარყოფილ წიბოებს: ორივე ბოლო უკვე ერთ კომპონენტშია. პრიმის ფაზაში სცადე სხვა საწყისი წვერო: ჯამი მაინც 39-ია.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →
✎ შენი მონაცემებიკრასკალს საწყისი წვერო არ სჭირდება; პრიმი მისგან იზრდება. ნებისმიერი საწყისით ჯამი იგივეა: 39.

კრასკალი: დალაგებული წიბოები · ჯამური წონა: 0

75897515689111234567

კრასკალი: დალაგებული წიბოები

1-4 (5)3-5 (5)4-6 (6)1-2 (7)2-5 (7)2-3 (8)5-6 (8)2-4 (9)5-7 (9)6-7 (11)4-5 (15)
დამფარავი ხე ყველა წვეროს აკავშირებს ციკლების გარეშე; მინიმალურს უმცირესი ჯამური წონა აქვს. კრასკალი ყველა წიბოს წონით ალაგებს და უიაფესს ამატებს, რომელიც აციკლური რჩება.

ფსევდოკოდი

 1 Kruskal: sort edges ascending by weight 2   for each edge (u,v): if u,v in different sets (DSU) 3     accept it and union; else it would form a cycle → reject 4   stop after V-1 edges 5 Prim: grow a tree from one vertex, 6   repeatedly add the lightest edge crossing the cut
1 / 1
03

შეამოწმე

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

№1

ბმულ გრაფს 10 წვერო და 25 წიბო აქვს. რამდენი წიბოა მის მინიმალურ დამფარავ ხეში?

№2

კრასკალი მივიდა 2-3 წიბოსთან (წონა 8), და find(2) == find(3). რა ხდება?

№3

პრიმმა ამოიღო u და განიხილავს წიბოს (u, v, w), სადაც v ხის გარეთაა. როგორ ანახლებს v-ს?

04

ივარჯიშე

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

LeetCodeMin Cost to Connect All Points საშუალო↗CSESRoad Reparation საშუალო↗LeetCodeFind Critical and Pseudo-Critical Edges in Minimum Spanning Tree მოწინავე↗