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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש


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


כדאי לדעת:

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



Page white cplusplus.png

מימוש 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, ברור שהצומת מוכנס לתור במהלך שלב זה.

מש"ל.PNG

ניתוח סיבוכיות[עריכה]

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

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

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

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

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

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