პრიმის ალგორითმი / Prim’s Algorithm

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

ფსევდოკოდი 

  • A იყოს ბმული , შეწონილი გრაფი V წყვეროთა და E წიბოთა სიმრავლით . 
  • V(new) = {x} x არის საწყისი წვერო რომელიც ეკუთვნის V-ს , E(new) = {} 
  • შემდეგი ოპერაციები გაიმეორე სანამ V(new) = V; //ანუ სანამ ყველა წვეროს არ შემოვივლით
  • აირჩიე (u,v) წიბო მინიმალური წონისა ისეთი რომ u ეკუთვნის V(new)-ს და v არ ეკუთვნის;
  • დაამატე v წვერო V(new) წვეროთა სიმრავლეს და (u,v ) წიბო E(new) წიბოთა სიმრავლეს ;
  • შედეგად  V(new) და  E(new) აღწერს მინიმალურ დამფარავ ხეს

მუშაობის დრო

მარტივი იმპლემენტაცია მასივისთვის მოითხოვს მინიმალური წონის წიბოს მოძებნას და მისი მუშაობის ზედა ზღვარი არის O(V^2) , ორობითი გროვის გამოყენებისას და ბმული სიის დროს პრიმის ალგორითმის მუშაობის შედა ზღვარია        O(E*logV) , სადაც E წიბოების რაოდენობაა, ხოლო V წყვეროებისა. 

სისწორის დამტკიცება

ვთქვათ P არის ბმული შეწონილი გრაფი . პრიმის ალგორითმის ყოველ იტერაციაზე ისეთი წიბო უნდა ვიპოვოთ რომელიც აკავშირებს გრაფის შიგა და გარე წვეროებს. სანამ P არის ბმული , ყოველთვისმ ოიძებნება გზა ყველა წვერომდე . პრიმის ალგორითმის შედეგი არის ხე , რადგან წვეროები და წიბოები ემატება Y ხეს . ვთქვათ Y1 არის P გრაფის მინიმალური დამფარავი ხე . e იყოს პირველი წიბო რომელიც დაემატა  Y ხეს მაგრამ არ არის  Y1 ხეში და V არის წვეროები ისეთი წიბოებით დაკავშირებული ,რომლებიც e-ს დამატებამდე დაემატა. სანამ  Y1 არის P გრაფის მინიმალური დამფარავი ხე , მაშინ არის გზა  Y1 -ში რომელიც აერთებს ორ უკანასკნელ წვეროს. f იყოს ერთ-ერთი წიბო რომელიც ალგორითმის შესრულების პროცესში შეგვხვდა და თუ მისი წონა ნაკლებია e-ს წონაზე მაშინ მან ჩაანაცვლოს e . სანამ f წიბო არ დამატდება ხეს ჩვენ ვიცით რომ w(f) >= w(e) . 

ახლა ვთქვათ Y2 არის გრაფი მიღებული f წიბოს წაშლითა და e-ს ჩამატებით  Y1 -ში. ადვილი დასანახია რომ  Y2-იც არის ბმული გრაფი და აქვს იმდენივე წიბო რამდენიც  Y1 -ს. ამასთანავე მისი წონა არ აღემატება  Y1 -ის წონას, ამიტომ ისიც არის მინიმალური დამფარავი ხე P გრაფისა რომელიც შეიცავს e წიბოს და ყველა სხვა წიბოს რომელიც e-ს დამატებამდე გავიარეთ . გავიმეოროთ ზემოთ ჩატარებული ოპერაციები და მივიღებთ P გრაფის მინიმალურ დამფარავ ხეს , რომელიც  Y-ის იდენტრი იქნება . ეს კი იმას ნიშნავს რომ  Y არის მინიმალური დამფარავი ხე . 

 

3 thoughts on “პრიმის ალგორითმი / Prim’s Algorithm

  1. ჯიგარი პოსტია!
    ახლა მივხვდი რომ ორი სიმრავლის გაერთიანებით ბოლოს მინიმალურ დამფარავ ხეს ვიღებთ და მორჩა ამბავი.🙂 Спосибо автору!

  2. გაიხარე ავტორ!
    დეიქსტრაზეც და კრასკალზეც თუ დაპოსტავ ეგრე უფრო მადლიერი დაგრჩები.

    • დეიქსტრაზე დევს ვიდეო გაკვეთილი და გამოგადგება

Leave a Reply / უპასუხე

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / შეცვლა )

Twitter picture

You are commenting using your Twitter account. Log Out / შეცვლა )

Facebook photo

You are commenting using your Facebook account. Log Out / შეცვლა )

Google+ photo

You are commenting using your Google+ account. Log Out / შეცვლა )

Connecting to %s