מוטיבציה

בעוד Kruskal ממיין את כל הקשתות באופן גלובלי ומשתמש במבנה union-find, Prim מחזיק עץ יחיד שהולך וגדל, ומגיע שוב ושוב אל הקודקוד החיצוני הקרוב ביותר.

למה ללמוד את Prim?

• גרפים צפופים: Prim יעיל כשיש הרבה קשתות, אם משתמשים במבני הנתונים המתאימים.
• תכונת החתך: הוא ממחיש באופן מעשי מדוע תמיד בטוח להוסיף את הקשת הזולה ביותר שיוצאת מהעץ הנוכחי.
• שתי נקודות מבט על בעיה אחת: השוואה בין Prim ל-Kruskal מעמיקה את ההבנה שלך של עצים פורשים מינימליים.

מכיוון שלכל העצים הפורשים המינימליים של גרף יש אותן משקולות קשתות, Prim ו-Kruskal תמיד מדווחים על אותה משקולת כוללת.