BFS

אחד האלגוריתמים הפשוטים לחיפוש גרפים, ולביצוע SSSP .
בהינתן גרף $G=(V,E)$ וקודקוד מקור $s\in V$ , $BFS$ עובר בצורה סיסטמטית על קשתות הגרף ומבקר בכל קודקוד $v$ הנגיש מ $s$ (נגיש = קיים מסלול).
תוך כדי האלגוריתם מחשב את המרחק (מספר הקשתות במסלול) מ$s$ לכל קודקוד נגיש, נוכיח בהמשך שזה המסלול הקצר ביותר. בנוסף הוא מייצר עץ רוחב Breadth-First Tree או עץ מסלולים ששורשו $s$ שמכיל את כל הקודקודים והמסלולים הפשוטים הנגישים מ $s$.

כמה דגשים חשובים:
א) האלגוריתם עובד עם גרף מכוון ולא מכוון. ללא פונקציית משקל.
ב) האלגוריתם מבקש בקודקודים במרחק $k$ מ $s$ לפני אלה שנמצאים במרחק $k+1$

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

עבור קשת $(u,v)\in E$ אם $u$ שחור אז בהכרח $v$ או אפור או שחור לפי מה שאמרנו.
כמו כן, נשייך לכל קודקוד ערך $\pi$ המהווה קודקוד האבא בעץ הרוחב. כל הקודקודים מתחילים עם $\pi =NULL$ וכשנציב ערך , הוא לא ישתנה לאורך כל האלגוריתם.
בנוסף בדומה לאלגוריתמים נוספים שמחשבים את ה SSSP , לכל קודקוד משוייך ערך d שבסיום הריצה יכיל את המרחק המינימלי של הקודקוד הזה מ $s$, ואם אין כזה הערך יישאר $\mathrm{\infty }$ .

BFS(G,s)
	for each u in V-{s}:
		u.color = WHITE
		u.d = ∞
		u.𝝅 = NIL
	s.color = GRAY
	s.d = 0
	s.𝝅 = NIL
	Q= {}
	Q.enqueue(s)
	while Q != {}:
		u = Q.dequeue()
		for each v in adj(u):
			if v.color == WHITE
				v.color = GRAY
				v.d = u.d + 1
				v.𝝅 = u
				Q.enqueue(v)
		u.color = BLACK

• האלגוריתם מניח ש $G$ מיוצג על ידי רשימת שכנויות
• $Q$ הוא תור FIFO.

זמן ריצה

בגלל שלאחר האתחול האלגוריתם לא צובע אף קודקוד בצבע לבן אנחנו מבטיחים שהתנאי if color == white יתקיים עבור כל קודקוד פעם אחת בידיוק.
פעולת הכנסה והוצאה הן בעלות קבועה $O(1)$ וזאת קוראת לכל קודקוד את כל שכניו כלומר $O(E)$ עבור כל הקודקודים. לכן הפעולה הזאת $+$ פעולת האתחול שלוקחת $O(V)$ אומר שהאלגוריתם BFS יעלה לנו:

מסלולים קצרים ביותר

נרצה להוכיח שבסיום ריצת $BFS$ עבור קודקוד מקור $s$ מתקיים

ואם אין מסלול אז הערך הוא $\mathrm{\infty }$ .

נוכיח כעת כמה למות שיעזרו לנו בשביל ההוכחה שBFS מביא את המסלולים הקצרים ביותר עבור גרף לא ממושקל:

אי שיוויון המשולש

יהי $G=(V,E)$ גרף מכוון או לא מכוון ויהי קודקוד מקור $s$. אזי

הוכחה:

• אם u לא נגיש מ s אז $\delta (s,u)=\mathrm{\infty }$ והטענה מתקיימת.
• אם u נגיש מ s אז גם v. נניח בשלילה $\delta (s,v)>\delta (s,u)+1$
  נגדיר את P המסלול הקצר ביותר מ $s$ ל $u$ ולכן אורכו $\delta (s,u)$ אזי אם נוסיף את $v$ למסלול הזה נקבל שאורכו $\delta (s,u)+1$ , וזה אורך מסלול מ $s$ ל $v$ שקצר יותר מ $\delta (s,v)$ בסתירה למינימליות של מסלול קצר ביותר.

חסם עליון

יהי $G=(V,E)$ גרף מכוון או לא מכוון ויהי קודקוד מקור $s$. אזי בסיום ריצת BFS

הוכחה:
באינדוקצייה על מספר פעולות ההכנסה לתור.
בסיס- הפעולה הראשונה היא הכנסת $s$. בזמן זה מתקיים $0=\delta (s,s)=s.d$ וכל שאר הקודקודים מקיימים $v.d=\mathrm{\infty }$ ולכן הנ״ל מתקיים בשלב זה.

צעד - נניח שהטענה נכונה לאחר הכנסת $k$ קודקודים לתור. נוכיח שהטענה נכונה עבור הקודקוד ה $k+1$ . נסמן את הקודקוד הזה ב $v$ , שהוכנס תוך כדי סריקת רשימת השכנויות של $u$ .
לפי הנחת האינדוקצייה

לפי אי שיוויון המשולש ולפי הנחת האינדוקצייה

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

לכל היותר שני ערכי d שונים בתור בכל רגע

נניח שבמהלך ריצת BFS על הגרף , התור $Q$ מכיל את הקודקודים $[v_1,v_2\dots ,v_r]$ כאשר $v_1$ הוא ראש התור. אזי:

א) $v_r.d\le v_1.d+1$
ב) ${\mathrm{\forall }}_{1\le i\le r}:v_i.d\le v_{i+1}.d$

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

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

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

וגם מתקיים

זה הוכחה של סעיף א.
נכונות של סעיף ב נובעת מכך שלפי הנחת האינדוקצייה $v_2.d\le v_3.d$ גם כ $v_1$ היה בתור והוצאתו לא שינתה ערכים ולכן היחס סדר הזה עדיין נשמר.

הכנסה = נסמן $v_{r+1}$ כקודקוד שנכנס לסוף התור. כדי להגיע להכנסה הזאת הוצאנו קודקוד $u$ שהוא אבא של $v_{r+1}$ . מהנחת האינדוקצייה יתקיים עבור הראש החדש של התור ש

וזה בלי קשר למתי $v_1$ נכנס לתור, כלומר לא משנה האם הוא היה בתור בזמן הוצאת $u$ או שהוא נכנס לתור כתוצאה מסריקת השכנים.

מהאלגוריתם מתקיים

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

ולכן

כיוון שמהנחת האינדוקצייה אנחנו יודעים שלכל $j<r$ מתקיים $v_j.d\le v_{r+1}.d$ אז סיימנו כעת גם להוכיח את סעיף ב.

מסקנה נניח ש $v_i$ נכנס לפני $v_j$ לתור במהלך BFS אזי

זה מסתדר עם העובדה שאנחנו סורקים לרוחב את הגרף כלומר מתחילים מהשכנים המיידים של $s$ ומעלים את d עבורם ב 1 וכן הלאה ממשיכים לשכנים שלהם עד שמגיעים לקודקודים ה״רחוקים״ ביותר מ $s$ .

נכונות BFS

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

כמו כן נוכיח שאחד המסלולים הקצרים ביותר מ $s$ ל $v$ הוא המסלול הקצר ביותר מ $s$ ל $v.\pi$ עם הוספת הקשת $(v.\pi ,v)$ .

נב״שׁ שקיים קודקוד $v\in V$ כך ש $v.d\ne \delta (s,v)$ בסוף האלגוריתם.
בדומה להוכחה ב SSSP אנחנו יודעים להגיד ש $s\ne v$ וש $v.d>\delta (s,v)$ , כלומר , קיים מסלול בין $s$ ל $v$ (אחרת הערך היה $\mathrm{\infty }$ ומהלמות שהוכחנו למעלה ערך זה לא משתנה בסתירה להנחה שלנו).
נסמן את $u$ הקודקוד הקודם של $v$ במסלול הקצר ביותר שאורכו $\delta (s,v)$ ולכן

כעת נבין מה קורה כשמוציאים את $u$ מהתור. בזמן הזה $v$ יכול להיות צבוע באחד משלושת הצבעים

א) אם הוא לבן: אז נקבל שבבדיקת שכני $u$ נעשה השמה $v.d=u.d+1$ בסתירה.
ב) אם הוא שחור: זאת אומרת שהוצאנו מהתור לפני שהוצאנו את $u$ ולכן מהמסקנה שהוכחנו, $v.d\le u.d$ בסתירה.
ג) אם הוא אפור: אז קיים קודקוד $w$ כך ש $v.\pi =w$ ואז $v.d=w.d+1$ ולפי אותה מסקנה שהראנו $w.d\le u.d$ כלומר $v.d\le u.d+1$ בסתירה.

סך הכל הוכחנו שלכל קודקוד יתקיים $v.d=\delta (s,v)$ בסוף האלגוריתם כדרוש.
כמו כן כאשר האבא של $v$ הוא $u$ אז נקבל בשורת ההשמה של האלגוריתם

כלומר שהמסלול הקצר ביותר מ $s$ ל $v$ הוא המסלול הקצר ביותר מ $s$ ל $u$ פלוס 1.

עץ הרוחב

BFS בונה עץ רוחב במהלך ריצתו ביחס לערכי $\pi$ .
נגדיר Predecessor subgraph של $G$ להיות תת הגרף $G_{\pi }(V_{\pi },E_{\pi })$ כאשר:

תת הגרף הוא עץ הרוחב של $G$ עם שורש $s$ וכל הקודקודים הנגישים ממנו. כמו כן לכל הקודקודים ב $V_{\pi }$ מתקיים שתת הגרף הזה מכיל מסלול ייחודי מ $s$ ל $v$ שאורכו $\delta (s,v)$ כלומר מסלול קצר ביותר בגרף המקורי.

ההוכחה שאכן עץ הרוחב הוא תת הגרף הזה נובעת ישירות מהאלגוריתם אנחנו יודעים שהאלגוריתם מגדיר

כלומר ההשמה הזאת מתרחשת רק אם היחס בינהם הוא שהם מרכיבים קשת וגם $v$ נגיש מ $s$ . מהשמה זאת ומהוכחת הנכונות של BFS אנחנו יודעים שבסופו של האלגוריתם כל הקודקודים שיסומנו בשחור ירכיבו את המסלולים הקצרים ביותר מ $s$ לכל הקודקודים האחרים ומהגדרת $G_{\pi }$ הוא עץ ולכן מכיל מסלול פשוט ייחודי מ $s$ לכל הקודקודים הנגישים.

הדפסת מסלול קצר ביותר

הפרוצדורה הבאה מדפיסה את הקודקודים הנמצאים על המסלול מ $s$ ל $v$ :

print_path(G,s,v) 
	if v==s
		print s
	else if v.𝜋 == Nil 
		no path from s to v exists
	else print_path(G,s,v.𝜋)
		print v