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


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


כדאי לדעת:

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



מימוש C++

boost::breadth_first_search


הבעיה

עריכה

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




דוגמה:

בגרף הבא, נניח צומת מוצא  .


 
בעיית החיפוש הרוחבי.


רוצים למצא את המסלול הקצר ביותר מ  לכל צומת אחר בגרף. המסלול הקצר ביותר ל , לדוגמה, הוא  , וארכו 2.


חיפוש רחבי

עריכה

הרעיון הכללי

עריכה

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

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

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

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



דוגמה:

עבור הגרף שראינו לעיל, וצומת המוצא  , הנה המצב ההתחלתי:

 
מצב התחלתי בחיפוש רוחבי.


כעת 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 מכיל בכל עת סדרת צמתים מהצורה  , עבור   כלשהם, כך ש:

  1. Min-Dists[u1] = ... = Min-Dists[ui] =  
  2. Min-Dists[v1] = ... = Min-Dists[vj] =  

עבור   כלשהו.


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




דוגמה:

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



הגדרה:

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




דוגמה:

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


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

עריכה

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



משפט:

כאשר q מגיע לשלב  , אז q מכיל בדיוק את הצמתים שמרחקם הקצר ביותר מs הוא  .


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

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

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


הוכחה: ההוכחה היא באינדוקציה על  .

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

(מעבר האינדוקציה) נניח שהטענה נכונה עד לשלב ה  (כולל), ונראה שהיא נכונה לשלב ה .

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

כעת ניקח צומת   כלשהו (לא הצומת הקודם), שמרחקו מ  הוא  . אם זה המצב, אז קיים   כלשהו כך שקיים מסלול מ  ל  כלשהו באורך  , וכן יש קשת מ  ל . (למעשה, ייתכן יותר מצומת יחיד כזה. נקרא בשם   לצומת הראשון המקיים זאת.) לפי הנחת האינדוקציה,   היה בתור בשורה 6 בשלב  . אבל מ8-11, ברור שהצומת   מוכנס לתור במהלך שלב זה.

 

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

עריכה

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

1-2 פועלות בבירור בזמן  .

3-5 מבצעות   פעולות Enqueue, ולכן אורכות זמן   במקרה הגרוע.

כפי שראינו, כל צומת נכנס לכל היותר פעם אחת לq, ולכן 6-11 רצה לכל היותר   פעמים. 7 היא  , ולכן תורמת סה"כ‏  .‏ 8-11 רצות   פעמים לכל צומת u, ולכן רצות סה"כ ‏  פעמים לכל היותר. 9-11 הן  , ולכן תורמות סה"כ ‏ .

הסיבוכיות, לכן, היא   במקרה הגרוע.

הפרק הקודם:
אלגוריתם Prim
חיפוש רוחבי
תרגילים
הפרק הבא:
אלגוריתם Dijkstra