מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/מבני נתונים לקבוצות זרות

תבנית:מבנה תבנית

דף זה עוסק במניפולציות שונות של מבני נתונים המתארים קבוצות זרות זו לזו.

הבעיה

מייצרים $n$ קבוצות זרות, כל אחת בת איבר יחיד. כעת מאחדים בכל פעם שתי קבוצות כלשהן. במהלך סדרת האיחודים ולאחריהם רוצים לשאול, בהנתן שני איברים, האם הם חלק מאותה קבוצה או לא.

תבנית:מבנה תבנית

ממשק

הפסוודו-קוד הבא מראה את הממשק של מבנה הנתונים שבו נשתמש לבעיה כזו שראינו:

# Makes a set.
Make-Set()

# Finds a set by a "representative" (u).
Find-Set(u)

# Joins two sets by their "representatives" (u, v).
Union(u, v)

הנה הפסוודו-קוד המראה כיצד להשתמש בממשק:

1	t1 = Make-Set()
2	t2 = Make-Set()
3	t3 = Make-Set()
4	t4 = Make-Set()
5	t5 = Make-Set()
6	t6 = Make-Set()
7	t7 = Make-Set()
8	t8 = Make-Set()
	
9	Union(t1, t2)
10	Union(t3, t4)
11	Union(t5, t6)	
12	Union(t2, t5)
13	Union(t8, t2)

	# Prints True.
14	Print( Find-Set(t1) == Find-Set(t6) )

	# Prints False.
15	Print( Find-Set(t1) == Find-Set(t7) )

מבני נתונים ואלגוריתמים - מחברת קורס/ADT

הנחות ומטרה

נתבונן בסדרת פעולות שכ"א מהן היא תבנית:קוד בשורה, תבנית:קוד בשורה, או תבנית:קוד בשורה.

1. נגדיר את $m$ כמספר הפעולות בסדרה.
2. נגדיר את $n$ כמספר פעולות תבנית:קוד בשורה בסדרה (נשים לב שבהכרח $n\le m$).

תבנית:מבנה תבנית

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

מטרתנו היא למצוא מימוש כך שסדרת הפעולות תעלה סה"כ $O(n\log (n)+m)$ במקרה הגרוע (אם כי, במימושים אחרים נראה שאפשר אף להגיע ליעילות טובה יותר).

מימוש רשימות נאיבי

הרעיון הכללי

נחזיק מערך גלובאלי, תבנית:קוד בשורה, של רשימות מקושרות. כל חוליה תציין נציג של קבוצה כלשהו, וכל רשימה מקושרת תציין קבוצה מאוחדת.

תבנית:קוד בשורה

הנה הפסוודו-קוד ל תבנית:קוד בשורה:

	# A global array of n Linked-lists.
1	Lists = Make-Array(n)

	# A global variable indicating how many sets were made.
2	size = 0


# Makes a set.
Make-Set()
	# Make a new list.
1	Lists[++size] = Make-List()

	# Insert in a link whose value is size.
2	Insert-Front(Lists[size], size)

	# Return the (pointer to the) first link.
3	return Lists[size].front

המערך הגלובאלי תבנית:קוד בשורה (בשורה 1) משמש לשמירת הרשימות - תבנית:קוד בשורה הוא מערך של רשימות מקשורת. המשתנה הגלובאלי תבנית:קוד בשורה (בשורה 2) מתאר כמה קבוצות כבר ייצרנו; תבנית:קוד בשורה תמיד יהיה אינדקס המערך בו ניצור את הרשימה הבאה.

כעת נניח שמייצרים קבוצה חדשה (על ידי תבנית:קוד בשורה). שורה 1 של תבנית:קוד בשורה מייצרת רשימה מקושרת חדשה, ושומרת אותה במקום חדש במערך תבנית:קוד בשורה. שורה 2 דוחפת ערך לתחילת הרשימה, דבר שמייצר חוליה חדשה ברשימה החדשה, כמובן. נשים לב שהערך שאותו דוחפים הוא פשוט אינדקס הרשימה. שורה 3 פשוט מחזירה את החוליה החדשה (ברשימה המקושרת החדשה) כערך המוחזר.

תבנית:מבנה תבנית

תבנית:קוד בשורה

נניח שרוצים לאחד שתי קבוצות, תבנית:קוד בשורהו תבנית:קוד בשורה (ע"י תבנית:קוד בשורה).

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

1. ברשימה המקושרת תבנית:קוד בשורה, נעבור בלולאה ונשנה את ערכי כל האיברים לתבנית:קוד בשורה.
2. נאחד את שתי הרשימות המקושרות תבנית:קוד בשורה, ו תבנית:קוד בשורה, כך ש תבנית:קוד בשורהתקבל את כל החוליות, ו תבנית:קוד בשורה תאבד את החוליות שלה (כלומר תהפוך לריקה).

הנה הפסוודו-קוד לכך, ולאחריו שתי פונקציות עזר (הקשורות בכלל לרשימות מקושרות):

# Joins two sets by their "representatives" (u, v).
Union(u, v)
1	l_u = Lists[u.value]
2	l_v = Lists[v.value]

	# Set all values in l_v to be u.value.
	# (This is one lf List's utility functions).	
3	List-Set-All(l_v, u.value)
	
	# l_u becomes a list whose links are the union of the links
	# 	of (the old) l_u and l_v.
	# 	l_v becomes the empty list.
	# (This is one of List's utility functions).	
4	List-Union(l_u, l_v)

הנה שתי פונקציות העזר:

מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/רשימות מקושרות/פסוודו-קוד לList-Set-All

מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/רשימות מקושרות/פסוודו-קוד לList-Union

תבנית:מבנה תבנית

תבנית:מבנה תבנית

האינווריאנטה

מהתבוננות במימוש שתי הפעולות שראינו, קל לזהות את האינווריאנטה הבאה.

תבנית:משפט המשפט אומר למעשה את הדבר הבא. כל החוליות ברשימה המקושרת של תבנית:קוד בשורה בעלות הערך 1 בתבנית:קוד בשורה, כל החוליות ברשימה המקושרת של תבנית:קוד בשורה בעלות הערך 2 בתבנית:קוד בשורה, וכולי.

ראשית, קל לראות שהדבר נכון לכל חוליה שנוצרה כרגע ע"י תבנית:קוד בשורה.

כעת נוכיח את המשפט באינדוקציה.

ניתוח

קל להווכח בדברים הבאים:

מכאן קל לראות שמימוש זה אינו מתאים לדרישותינו המקוריות:

את המשפט תתבקש להוכיח בשיעורי הבית.

תבנית:קוד בשורה

כעת נותר לממש את תבנית:קוד בשורה, אבל זה קל: לפי האינווריאנטה שזה עתה ראינו, פשוט מחזירים את תבנית:קוד בשורה.

# Finds a set by a "representative"(u).
Find-Set(u)
1	return u.value

מימוש רשומות עם איחוד עפ"י גודל

הרעיון הכללי

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

תבנית:קוד בשורה

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

# Joins two sets by their "representatives" (u, v).
Union(u, v)
1	l_u = Lists[u.value]
2	l_v = Lists[v.value]

3	if Size(l_u) < Size(l_v) 
		# Exchange the lists.
4		l_u <-> l_v

	# Set all values in l_v to be u.value.
	#
	# (This is one lf List's utility functions).	
5	List-Set-All(l_v, u.value)
	
	# l_u becomes a list whose links are the union of the links
	# 	of (the old) l_u and l_v.
	# 	l_v becomes the empty list.
	#
	# (This is one lf List's utility functions).	
6	List-Union(l_u, l_v)'

תבנית:מבנה תבנית

ניתוח

קל להווכח בדברים הבאים:

כעת נראה סדרת משפטים המראה שמימוש זה מתאים לדרישותינו המקוריות.

נגדיר כ$T(n)$ את זמן הריצה הגרוע ביותר של סדרת פעולות תבנית:קוד בשורה המייצרות קבוצה בעלת גודל $n$ מ$n$ קבוצות זרות.

תבנית:משפט תבנית:הוכחה

אפשר לפתור נוסחה זו באמצעים אלגבריים (ראה שאלה זו).

הטענה הבאה קלה למדי.

כעת נוכל לנתח את סיבוכיות סדרת הפעולות.

תבנית:הוכחה

מימושים אחרים

ישנם מימושים אחרים שעבורם סדרת הפעולות תעלה רק $O(\alpha (n)+m)$ כאשר $\alpha$ היא הפונקציה ההפכית לפונקציית אקרמן, הגדלה באיטיות רבה מאד. הפונקציה גדלה כה לאט, שעבור ערכי $n$ מעשיים, $\alpha (n)$ הוא קבוע.

תבנית:מבני נתונים ואלגוריתמים - מחברת קורס