מוטיבציה

Kruskal שומר את היער ההולך וגדל של הקשתות שנבחרו במבנה איחוד-חיפוש. כדי להוסיף קשת בבטחה, הוא בודק אם שתי נקודות הקצה כבר נמצאות באותה קבוצה (דבר שייצור מעגל).

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

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

כל עצי השלד המינימליים של גרף משתמשים באותה רב-קבוצה של משקלי קשתות, ולכן המשקל הכולל (והקשת הגדולה ביותר) יחיד.