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

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

כדאי לדעת: בספר הקורס, הפרק "Elementary Graph Algorithms" (תת פרק 2) מכסה נושא זה, אולם אנו נשתמש בגרסה מעט פשוטה יותר מזו המופיעה בספר.

מימוש C++ boost::breadth_first_search

הבעיה

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

דוגמה: בגרף הבא, נניח צומת מוצא $\displaystyle s=1$. בעיית החיפוש הרוחבי. רוצים למצא את המסלול הקצר ביותר מ$\displaystyle s$ לכל צומת אחר בגרף. המסלול הקצר ביותר ל$\displaystyle 3$, לדוגמה, הוא $\displaystyle 1\rightarrow 2\rightarrow 3$, וארכו 2.

חיפוש רחבי

הרעיון הכללי

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

1. Min-Dists, מערך שיחזיק את המרחקים הקצרים ביותר.
2. q, תור שיחזיק את קבוצת הצמתים שאת מרחקיהם אנו קובעים כעת.

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

1. בתחילה נאתחל את כל איברי Min-Dists ל∞, למעט Min-Dists[s], שאותו נאתחל ל0; נכניס את s לq.
2. כל עוד q אינו ריק, נשלוף ממנו צומת, נעדכן את ערכי Min-Dists של שכניו, ונכניס אותם לתור עפ"י הצורך.

דוגמה: עבור הגרף שראינו לעיל, וצומת המוצא $\displaystyle s=1$, הנה המצב ההתחלתי: מצב התחלתי בחיפוש רוחבי. כעת 1 בראש התור. נשלוף אותו ונעדכן את שכניו. צעד 1 בחיפוש רוחבי. כעת 2 בראש התור. נשלוף אותו ונעדכן את שכניו. צעד 2 בחיפוש רוחבי. כעת 6 בראש התור. נשלוף אותו ונעדכן את שכניו. צעד 3 בחיפוש רוחבי. כעת 3 בראש התור. נשלוף אותו ונעדכן את שכניו. צעד 4 בחיפוש רוחבי. כעת 7 בראש התור. נשלוף אותו ונעדכן את שכניו. צעד 5 בחיפוש רוחבי. כעת 7 בראש התור, אבל אין את מי לעדכן - שכנו של 7 הוא 5, ול5 יש כבר מרחק ידוע של 3. לכן לא מכניסים את 5 לתור. ממשיכים כך הלאה עד שהתור מתרוקן.

פסוודו-קוד

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

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] )

הנה הסבר לBFS:

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

נכונות

משפט: ב11, Min-Dists מכיל את הערכים הנכונים.

שלבי התור

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

משפט: התור q מכיל בכל עת סדרת צמתים מהצורה $\displaystyle u_{1},...,u_{i},v_{1},...,v_{j}$, עבור $\displaystyle i,j\geq 0$ כלשהם, כך ש: Min-Dists[u1] = ... = Min-Dists[ui] = $\displaystyle k$ Min-Dists[v1] = ... = Min-Dists[vj] = $\displaystyle k+1$ עבור $\displaystyle k$ כלשהו.

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

דוגמה: בתחילת הדוגמה לעיל, הכיל q את הצומת 1, ואכן: Min-Dists[1] = $\displaystyle 0$. בדוגמה לעיל ראינו מצב שבו בq ישבו הצמתים 3, 7, 5, ואכן: Min-Dists[3] = $\displaystyle 2$ Min-Dists[7] = Min-Dists[5] = $\displaystyle 3$

הגדרה: נאמר שq מגיע לשלב $\displaystyle k$ בפעם הראשונה שבה בשורה 6, q מכיל צמתים שלכולם בדיוק אותו ערך $\displaystyle k$ בMin-Dists

דוגמה: בפעם הראשונה שמגיעים לשורה 6, הכיל q את הצומת 1, והיות שMin-Dists[1] = $\displaystyle 0$, אז q הגיע לשלב 0.

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

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

משפט: כאשר q מגיע לשלב $\displaystyle k$, אז q מכיל בדיוק את הצמתים שמרחקם הקצר ביותר מs הוא $\displaystyle k$.

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

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

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

הוכחה: ההוכחה היא באינדוקציה על $\displaystyle k$.

(בסיס האינדוקציה) q נמצא בשלב 0 כאשר $\displaystyle s$ מוכנס אליו. קל לראות שהטענה מתקיימת: אכן מרחקו הקצר ביותר מ$\displaystyle s$ ל$\displaystyle s$ הוא 0, ואין צומת אחר שמרחקו מ$\displaystyle s$ הוא 0.

(מעבר האינדוקציה) נניח שהטענה נכונה עד לשלב ה$\displaystyle k-1$ (כולל), ונראה שהיא נכונה לשלב ה$\displaystyle k$.

נתבונן בצומת $\displaystyle v$ שנמצא בתור בשלב $\displaystyle k$. נניח שמרחקו הקצר ביותר מ$\displaystyle s$ גדול ממש מ$\displaystyle k$. מתי הוכנס $\displaystyle v$ לתור? מתישהו בין שלב $\displaystyle k-1$ לשלב $\displaystyle k$, כאשר מצאנו שהוא שכן של צומת $\displaystyle u$ משלב $\displaystyle k-1$. אבל, לפי הנחת האינדוקציה, זה יש מסלול מ$\displaystyle s$ ל$\displaystyle u$ באורך $\displaystyle k-1$, ולכן יש מסלול מ$\displaystyle s$ ל$\displaystyle v$ באורך $\displaystyle k$. כלומר, אם $\displaystyle v$ בתור בשלב $\displaystyle k$, אז מרחקו לכל היותר $\displaystyle k$.

כעת ניקח צומת $\displaystyle v$ כלשהו (לא הצומת הקודם), שמרחקו מ$\displaystyle s$ הוא $\displaystyle k$. אם זה המצב, אז קיים $\displaystyle u$ כלשהו כך שקיים מסלול מ$\displaystyle s$ ל$\displaystyle u$ כלשהו באורך $\displaystyle k-1$, וכן יש קשת מ$\displaystyle u$ ל$\displaystyle v$. (למעשה, ייתכן יותר מצומת יחיד כזה. נקרא בשם $\displaystyle u$ לצומת הראשון המקיים זאת.) לפי הנחת האינדוקציה, $\displaystyle u$ היה בתור בשורה 6 בשלב $\displaystyle k-1$. אבל מ8-11, ברור שהצומת $\displaystyle v$ מוכנס לתור במהלך שלב זה.

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

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

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

3-5 מבצעות $\displaystyle |V|$ פעולות Enqueue, ולכן אורכות זמן $\displaystyle \Theta (|V|)$ במקרה הגרוע.

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

הסיבוכיות, לכן, היא $\displaystyle O(|V|+|E|)$ במקרה הגרוע.

הפרק הקודם: אלגוריתם Prim

חיפוש רוחבי תרגילים

הפרק הבא: אלגוריתם Dijkstra