האלגוריתם של קרוסקל ומבנה הנתונים Union/Find

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

אלגוריתמים לעץ פורש מינימלי בגרף – מה הרעיון הכללי?

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