מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם Union-Find/תרגילים/מספר הקריאות בהפעלת Connected-Components/תשובה

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

מהתבוננות בConnected-Components, ברור ש6 מתבצעת פעם אחת לכל קשת. מכאן נקבל שמספר הקריאות לFind-Set הוא .

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