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

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

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

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

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

כדאי לדעת:

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

מימוש C++

boost::breadth_first_search

תוכן עניינים

1 הבעיה
2 חיפוש רחבי
- 2.1 הרעיון הכללי
- 2.2 פסוודו-קוד
3 נכונות
- 3.1 שלבי התור
- 3.2 הוכחת הנכונות בעזרת שלבי התור
4 ניתוח סיבוכיות

[עריכה] הבעיה

נתונים גרף מכוון $\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$ , וארכו 3.

[עריכה] חיפוש רחבי

[עריכה] הרעיון הכללי

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

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

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

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

דוגמה:

עבור הגרף שראינו לעיל, וצומת המוצא $\displaystyle s = 1$ , הנה המצב ההתחלתי:

כעת 1 בראש התור. נשלוף אותו ונעדכן את שכניו.

כעת 2 בראש התור. נשלוף אותו ונעדכן את שכניו.

כעת 6 בראש התור. נשלוף אותו ונעדכן את שכניו.

כעת 3 בראש התור. נשלוף אותו ונעדכן את שכניו.

כעת 7 בראש התור. נשלוף אותו ונעדכן את שכניו.

כעת 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 \ge 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, ואכן:
1. Min-Dists[3] = $\displaystyle 2$
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$ .

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

כאשר q מגיע לשלב $\displaystyle k$ , אז מרחקו הקצר ביותר של כל צומת בq הוא $\displaystyle k$ .
אם מרחקו הקצר ביותר של צומת ב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|)$ .