איחוד קבוצות זרות
ויקיפדיה האנציקלופדיה encyclopedia
במדעי המחשב, איחוד קבוצות זרות (באנגלית: Disjoint-Set Data Structure), הוא מבנה נתונים אשר מבצע מעקב אחרי קבוצה של עצמים המחולקים למספר של תתי-קבוצות זרות ולא חופפות.
אלגוריתם איחוד-חיפוש (באנגלית: Union-Find Algorithm), הוא אלגוריתם המבצע את שתי הפעולות השימושיות הבאות על מבנה נתונים זה:
- חיפוש (Find): קביעה איזו קבוצה מכילה עצם ספציפי. פעולה זו יכולה גם לעזור בקביעה האם שני עצמים שייכים לאותה הקבוצה.
- איחוד (Union): איחוד שתי קבוצות לכדי קבוצה אחת.
פעולה הכרחית נוספת היא יצירה (MakeSet), פעולה היוצרת קבוצה חדשה המכילה עצם אחד בלבד (סינגלטון).
על מנת להגדיר פעולות אלו בצורה מדויקת יותר, נדרשת דרך לייצוג הקבוצות במבנה הנתונים. גישה שכיחה אחת היא בחירת עצם אחד מכל קבוצה להוות נציג, אשר תפקידו לייצג את הקבוצה כולה. הפעלת חיפוש על עצם , תחזיר את הנציג של הקבוצה אליה שייך. באופן דומה, פעולת איחוד תקבל שני נציגים כארגומנטים. בהמשך הדיון נעבוד תחת ההנחה שלא ניתן למחוק או להסיר עצמים ממבנה הנתונים.