სხვაობა კრუსკალსა და პრიმს შორის

2024 ავტორი: Alex Aldridge | [email protected]. ბოლოს შეცვლილი: 2023-12-17 13:43

კრუსკალი vs პრიმი

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

მეტი პრიმის ალგორითმის შესახებ

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

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

2. განვიხილოთ ხის კვანძებთან დაკავშირებული თითოეული კიდის წონა და აირჩიეთ მინიმალური. დაამატეთ ზღვარი და კვანძი T ხის მეორე ბოლოში და ამოიღეთ კიდე გრაფიკიდან. (აირჩიეთ რომელიმე, თუ არსებობს ორი ან მეტი მინიმუმი)

3. გაიმეორეთ ნაბიჯი 2, სანამ ხეს არ დაემატება n-1 კიდეები.

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

მეტი კრუსკალის ალგორითმის შესახებ

ჯოზეფ კრუსკალის მიერ შემუშავებული ალგორითმი გამოჩნდა ამერიკის მათემატიკური საზოგადოების მუშაობაში 1956 წელს. კრუსკალის ალგორითმი ასევე შეიძლება გამოიხატოს სამი მარტივი ნაბიჯით.

მოცემულია გრაფიკი n კვანძით და თითოეული კიდის შესაბამისი წონით, 1. აირჩიეთ რკალი მთელი გრაფიკის უმცირესი წონით და დაამატეთ ხეს და წაშალეთ გრაფიკიდან.

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

3. გაიმეორეთ პროცესი მე-2 საფეხურზე.

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

რა განსხვავებაა კრუსკალის და პრიმის ალგორითმს შორის?

• Prim-ის ალგორითმი ინიციალიზდება კვანძით, ხოლო კრუსკალის ალგორითმი იწყება კიდით.

• Prim-ის ალგორითმები ვრცელდება ერთი კვანძიდან მეორეზე, ხოლო კრუსკალის ალგორითმი ირჩევს კიდეებს ისე, რომ კიდეების პოზიცია არ იყოს დაფუძნებული ბოლო საფეხურზე.

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

• Prim-ის ალგორითმს აქვს დროის სირთულე O(V^{2), ხოლო კრუსკალის დროის სირთულე არის O(logV).}