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

דף זו עוסק באלגוריתם למציאת המסלול הקצר ביותר בגרף מכוון מצומת מוצא כלשהו.

תבנית:הארה

הבעיה

נתונים גרף מכוון $G=(V,E)$ וצומת מוצא $s\in V$ כלשהו. בהינתן צומת $v\in V$ כלשהו, רוצים לדעת מהו המסלול הקצר ביותר מ$s$ ל$v$.

חיפוש רחבי

הרעיון הכללי

במהלך מציאת הפתרון נחזיק שני מבני נתונים:

1. תבנית:קוד בשורה, מערך שיחזיק את המרחקים הקצרים ביותר.
2. תבנית:קוד בשורה, תור שיחזיק את קבוצת הצמתים שאת מרחקיהם אנו קובעים כעת.

נפעל עפ"י הצעדים הבאים:

1. בתחילה נאתחל את כל איברי תבנית:קוד בשורה לתבנית:קוד בשורה, למעט תבנית:קוד בשורה, שאותו נאתחל ל0; נכניס את תבנית:קוד בשורה לתבנית:קוד בשורה.
2. כל עוד תבנית:קוד בשורה אינו ריק, נשלוף ממנו צומת, נעדכן את ערכי תבנית:קוד בשורה של שכניו, ונכניס אותם לתור עפ"י הצורך.

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

פסוודו-קוד

להלן הפסוודו-קוד לחיפוש רחבי:

BFS(G, s)
1	q = Make-Queue()

2	Min-Dists = Make-Array( Length(V(G)) )

3	for u in V(G)
4		Min-Dists[u] = u == s? 0 : ∞
	
5	Enqueue(q, s)
	
6	while Size(q) > 0
7		u = Dequeue(q)
	
8		for v in A(G, u)
9			if Min-Dists[v] > Min-Dists[u] + 1
10				Min-Dists[v] = Min-Dists[u] + 1
11				Enqueue(q, v)
                	
12	return Min-Dists

ולהלן דוגמה לשימוש בו:

1	Min-Dists = BFS(G, 1)

	# Prints 0.
2	Print( Min-Dists[1] )

	# Prints 2.
3	Print( Min-Dists[3] )
	
	# Prints 3.
4	Print( Min-Dists[4] )

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

• ב1 מייצרים את את התור תבנית:קוד בשורה, וב2 מייצרים את את המערך תבנית:קוד בשורה.
• הלולאה 6-11 פועלת כל עוד תבנית:קוד בשורה אינו ריק.
• 7 מוציאה את האיבר הקדום ביותר שהוכנס ל בתבנית:קוד בשורה, ו8-11 מעדכנת את שכניו.

נכונות

שלבי התור

ראשית נוכיח את המשפט הבא, המתאר את מצב ההתור תבנית:קוד בשורה במהלך הלולאה 6-11.

תבנית:משפט

מה בעצם טוען המשפט?בלולאה 6-11, תבנית:קוד בשורה מכיל תמיד 0 או יותר צמתים שרשום להם מרחק כלשהו, שלאחריהם 0 או יותר צמתים שרשום להם מרחק גדול ב1. לעולם לא נראה בו זמנית בתבנית:קוד בשורה צמתים שלהם שלושה ערכים שונים בתבנית:קוד בשורה.

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

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

הוכחת הנכונות בעזרת שלבי התור

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

ראשית נשים לב שהמשפט למעשה אומר שני דברים:

1. כאשר תבנית:קוד בשורה מגיע לשלב $k$, אז מרחקו הקצר ביותר של כל צומת בתבנית:קוד בשורה הוא $k$.
2. אם מרחקו הקצר ביותר של צומת בתבנית:קוד בשורה הוא $k$, אז הצומת יהיה בתבנית:קוד בשורה כאשר תבנית:קוד בשורה מגיע לשלב $k$.

להלן הוכחת המשפט.

ניתוח סיבוכיות

נניח שהגרף נתון ברשימת שכנויות.

1-2 פועלות בבירור בזמן $\mathrm{\Theta }(|V|)$.

3-5 מבצעות $|V|$ פעולות תבנית:קוד בשורה, ולכן אורכות זמן $\mathrm{\Theta }(|V|)$ במקרה הגרוע.

כפי שראינו, כל צומת נכנס לכל היותר פעם אחת לתבנית:קוד בשורה, ולכן 6-11 רצה לכל היותר $|V|$ פעמים. 7 היא $O(1)$, ולכן תורמת סה"כ‏ $O(|V|)$.‏ 8-11 רצות $|N(u)|$ פעמים לכל צומת תבנית:קוד בשורה, ולכן רצות סה"כ ‏$|E|$ פעמים לכל היותר. 9-11 הן $O(1)$, ולכן תורמות סה"כ ‏$O(|E|)$.

הסיבוכיות, לכן, היא $O(|V|+|E|)$ במקרה הגרוע. תבנית:מבני נתונים ואלגוריתמים - מחברת קורס