גרפים›ייצוג גרפים

שאלה 5 במסלול אלגוריתמים. לפניכם גרף לא מכוון דו-צדדי G = (A, B, E):

צמתים בצד A: A = {A1, A2, A3}
צמתים בצד B: B = {B1, B2, B3}
קשתות בין A ל-B: E = {(A1–B1), (A1–B2), (A2–B1), (A2–B2), (A2–B3), (A3–B1), (A3–B2)}

(רשימת הקשתות מודפסת במפורש בטבלה שבעמוד 12 — היא אינה שחזור מן האיור.)

side A:    A1        A2        A3
side B:    B1        B2        B3

edges: A1-B1, A1-B2, A2-B1, A2-B2, A2-B3, A3-B1, A3-B2

B1 is joined to A1, A2, A3
B2 is joined to A1, A2, A3
B3 is joined to A2 only

סעיף ב — נתונה רשימה של חלק מן הקשתות: L = {(A1–B1), (A2–B2)}. "צומת תפוס" הוא צומת שמופיע ברשימה L (A1, A2, B1, B2). "צומת חופשי" הוא צומת שאינו מופיע ב-L (A3, B3).

האלגוריתם Path(G, L):

שלב אתחול: תור q שאליו מכניסים את הצומת A3; מערך visited בגודל 6 שבו בתא של A3 כתוב "כן" ובשאר "לא"; מערך parent בגודל 6 שכל תאיו ריקים.

שלב הרצה: כל עוד התור אינו ריק —

מוציאים את הצומת שבראש התור וקוראים לו U.
אם U נמצא בצד B וגם הוא "צומת חופשי" — האלגוריתם מחזיר את רשימת הצמתים U, ההורה של U, ההורה של ההורה של U וכן הלאה עד לצומת שאין לו הורה, ומסתיים.
אחרת (U בצד A, או U הוא "צומת תפוס") — בעבור כל שכן M של U: אם visited[M] = לא וגם מתקיים אחד מן התנאים
- U בצד A והקשת (U–M) אינה נמצאת ברשימה L, או
- U בצד B והקשת (U–M) נמצאת ברשימה L,
אז מכניסים את M לתור, כותבים "כן" בתא של M ב-visited, ורושמים ש-U הוא ההורה של M ב-parent.
אם התור התרוקן — מחזירים null.

גרף דו-צדדי: צד A={A1,A2,A3}, צד B={B1,B2,B3}. קשתות: A1-B1,A1-B2,A2-B1,A2-B2,A2-B3,A3-B1,A3-B2.

A1---B1
  \ /|
   X |
  / \|
A2---B2
  \  /
   \/
A3-B1(also), A3-B2
Edges: (A1,B1) (A1,B2) (A2,B1) (A2,B2) (A2,B3) (A3,B1) (A3,B2)

סעיף א

הצומת M מוגדר "שכן" של הצומת U, אם יש קשת ביניהם. לפניכם טבלת שכנויות המציגה את השכנים של כל צומת בגרף G. הצמתים השכנים של A1 ושל B1 נתונים בטבלה. השלימו את הטבלה.

סעיף ב

נתונה רשימה של חלק מן הקשתות בגרף G: L = {(A1-B1), (A2-B2)}. "צומת תפוס" הוא צומת שמופיע ברשימה L (הצמתים A1,A2,B1,B2 מופיעים ולכן הם "צמתים תפוסים"). "צומת חופשי" הוא צומת שאינו מופיע ברשימה L (הצמתים A3,B3 אינם מופיעים ולכן הם "צמתים חופשיים"). נתון האלגוריתם Path(G,L). שלב אתחול נתונים באלגוריתם: 1. נגדיר תור q, שאליו נכניס את הצומת A3. שימו לב: במהלך ריצת האלגוריתם ייכנסו לתור צמתים נוספים השייכים לצד A או לצד B. 2. נגדיר מערך visited בגודל 6, ובו נסמן את כל הצמתים שבהם ביקרנו במהלך ריצת האלגוריתם (בהתחלה בתא של A3 מופיע הערך כן, ובשאר התאים במערך מופיע הערך לא). 3. נגדיר מערך parent בגודל 6, ובו נשמור בעבור כל צומת את ה"הורה" שלו, כלומר את הצומת שממנו הגענו אליו במהלך ריצת האלגוריתם (בהתחלה כל התאים במערך ריקים). שלב הרצת האלגוריתם: 1. כל עוד התור q אינו ריק: נוציא את הצומת הנמצא בראש התור, ונקרא לו U. נבדוק אם U נמצא בצד B והוא גם "צומת חופשי": אם כן - האלגוריתם מחזיר רשימת צמתים שהם U, ההורה של U, וההורה של ההורה של U וכן הלאה, עד הצומת שאין לו הורה (כלומר לצומת שהתא שלו ריק במערך parent), והאלגוריתם מסתיים. אם לא (כלומר אם U נמצא בצד A או אם U הוא "צומת תפוס") - בעבור כל צומת שכן M של הצומת U: אם עדיין לא ביקרנו בצומת M (visited[M]=לא), וגם אחד מן התנאים שלהלן מתקיים: - U בצד A והקשת (U-M) אינה נמצאת ברשימה L; - U בצד B והקשת (U-M) נמצאת ברשימה L; אז: א. נכניס את M לתור. ב. נכתוב את הערך כן בתא של M במערך visited. ג. נעדכן שהצומת U הוא ההורה של M במערך parent. 2. אם התור ריק, נחזיר null, והאלגוריתם מסתיים.

Path(G, L)

סעיף ב(המשך - טבלת מעקב)

עקבו בטבלת מעקב אחרי ריצת האלגוריתם Path על הגרף הנתון G, עם הרשימה L. המעקב צריך לכלול בכל איטרציה את הפריטים שלהלן: מצב התור; הצומת U שהוצאנו מן התור; מערך visited; מערך parent.

סעיף ג

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

שאלות ותגובות על השאלה

🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות

שאלו כאן — ותקבלו מענה מוסמך.

🎓 מרצה לתכנות עונה כאן — תקבלו מענה מקצועי

לתרגל עוד שאלות — חינם ←