הצומת M מוגדר "שכן" של הצומת U, אם יש קשת ביניהם.

לפניכם טבלת שכנויות המציגה את השכנים של כל צומת בגרף G. הצמתים השכנים של A1 ושל B1 נתונים בטבלה. השלימו את הטבלה.

נתונה רשימה של חלק מן הקשתות בגרף G: L = {(A1 - B1), (A2 - B2)}.

"צומת תפוס" הוא צומת שמופיע ברשימה L (הצמתים A1, A2, B1, B2 מופיעים ולכן הם צמתים תפוסיםצמתים תפוסיםצומת שמופיע ברשימה L).

"צומת חופשי" הוא צומת שאינו מופיע ברשימה L (הצמתים A3, B3 אינם מופיעים ולכן הם צמתים חופשייםצמתים חופשייםצומת שאינו מופיע ברשימה L).

נתון האלגוריתם Path (G, L).

שלב אתחול נתונים באלגוריתם:

1. נגדיר תור – q, שאליו נכניס את הצומת A3.

שימו לב

במהלך ריצת האלגוריתם ייכנסו לתור צמתים נוספים השייכים לצד A או לצד B.

2. נגדיר מערך – visited בגודל 6, ובו נסמן את כל הצמתים שבהם ביקרנו במהלך ריצת האלגוריתם (בהתחלה בתא של A3 מופיע הערך כן, ובשאר התאים במערך מופיע הערך לא).

3. נגדיר מערך – parent בגודל 6, ובו נשמור בעבור כל צומת את ה"הורה" שלו, כלומר את הצומת שממנו הגענו אליו במהלך ריצת האלגוריתם (בהתחלה כל התאים במערך ריקים).

שלב הרצת האלגוריתם:

1. כל עוד התור – q אינו ריק:
   • נוציא את הצומת הנמצא בראש התור, ונקרא לו U.
   • נבדוק אם U נמצא בצד B והוא גם צומת חופשיצומת חופשיצומת שאינו מופיע ברשימה L:

     • אם כן – האלגוריתם מחזיר רשימת צמתים שהם: U, ההורה של U וההורה של ההורה של U וכן הלאה, עד הצומת שאין לו הורה (כלומר לצומת שהתא שלו ריק במערך parent), והאלגוריתם מסתיים.

     • אם לא (כלומר אם U נמצא בצד A או אם U הוא צומת תפוסצומת תפוסצומת שמופיע ברשימה L) – בעבור כל צומת שכן – M של הצומת U: אם עדיין לא ביקרנו בצומת M (visited[M] = לא), וגם אחד מן התנאים שלהלן מתקיים:

       • U בצד A והקשת (U-M) אינה נמצאת ברשימה L
       • U בצד B והקשת (U-M) נמצאת ברשימה L

       אז:

       1. נכניס את M לתור.
       2. נכתוב את הערך כן בתא M במערך visited.
       3. נעדכן שהצומת U הוא ההורה של M במערך parent.
2. אם התור ריק, נחזיר null, והאלגוריתם מסתיים.

עקבו בטבלת מעקב אחרי ריצת האלגוריתם Path על הגרף הנתון G, עם הרשימה L.

המעקב צריך לכלול בכל איטרציה את הפריטים שלהלן:

• מצב התור
• הצומת U שהוצאנו מן התור
• מערך visited
• מערך parent

כתבו את רשימת הצמתים שהאלגוריתם מחזיר.