שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2017 - גרפים

קיומי זה רדודד שלוקו לעדודו בטיודה DFS וגם בטיודה BFS.

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

פתרון: כן, קיים גרף שעבורו סריקות BFS ו-DFS, המתחילות מאותו צומת, יפיקו את אותו **עץ פורש**. הדוגמה הכללית ביותר היא כל גרף שהוא **עץ** בעצמו. על פי הגדרה, עץ הוא גרף קשיר ללא מעגלים. לגרף כזה יש עץ פורש יחיד, והוא הגרף עצמו. לכן, כל אלגוריתם שמוצא עץ פורש (ובכלל זה **סריקת BFS** ו**סריקת DFS**) חייב להחזיר את הגרף המקורי, ולכן שני האלגוריתמים יחזירו את אותו העץ. דוגמה קונקרטית ופשוטה יותר היא **גרף מסלול** (path graph). יהי $G=(V,E)$ גרף מסלול עם $n$ צמתים, כלומר $V = \{v_1, v_2, ..., v_n\}$ וקשתות $E = \{(v_i, v_{i+1}) | 1 \le i < n\}$. נניח שמתחילים את שתי הסריקות מהצומת $v_1$. * **בסריקת BFS:** 1. האלגוריתם מתחיל ב-$v_1$. שכנו היחיד הוא $v_2$. התור מכיל את $v_2$, והקשת $(v_1, v_2)$ נוספת לעץ. 2. בשלב הבא, מוציאים את $v_2$ מהתור. שכנו היחיד שטרם בוקר הוא $v_3$. התור מכיל את $v_3$, והקשת $(v_2, v_3)$ נוספת לעץ. 3. התהליך ממשיך באופן סדרתי לאורך המסלול, כאשר בכל צומת $v_i$ יש רק שכן אחד, $v_{i+1}$, שטרם בוקר. העץ הפורש שמתקבל הוא המסלול המקורי: $v_1-v_2-...-v_n$. * **בסריקת DFS:** 1. האלגוריתם מתחיל ב-$v_1$. הוא מבקר אצל שכנו הראשון (והיחיד) $v_2$, ומוסיף את הקשת $(v_1, v_2)$ לעץ. 2. מ-$v_2$, האלגוריתם ממשיך רקורסיבית לשכנו היחיד שטרם בוקר, $v_3$, ומוסיף את הקשת $(v_2, v_3)$. 3. הרקרוסיה ממשיכה "להעמיק" לאורך המסלול עד הגעה לצומת $v_n$, מאחר שבכל שלב יש רק אפשרות התקדמות אחת. גם כאן, העץ הפורש שמתקבל הוא המסלול המקורי: $v_1-v_2-...-v_n$. מאחר ושתי הסריקות הפיקו את אותו עץ פורש (שהוא הגרף עצמו), הוכחנו כי גרף כזה קיים. $\blacksquare$