גרפים›מעבר על גרף

שאלה 5 במסלול אלגוריתמים. בסעיף א מפעילים DFS ואחר כך BFS מקודקוד a על גרף לא מכוון נתון ברשימת סמיכויות, ומשרטטים את שני עצי הסריקה. בסעיף ב, שאין לו קשר לסעיף א, גרף ממושקל בעל 7 קודקודים: מוצאים את המסלולים הקלים (הקצרים) מ-S לכל קודקוד באמצעות דייקסטרה, ומשרטטים את עץ המסלולים הקצרים.

גרף לא מכוון G=(V,E), רשימת סמיכויות (p-10.png top)

a:b,d,f; b:a,c,e; c:b,e,g; d:a,e; e:b,c,d,f; f:a,e,g; g:c,f

גרף לא מכוון ממושקל G (p-10.png bottom, 300dpi crop p10_weighted.png)

edges(weight): S-A(7) S-B(3) A-D(8) D-B(2) A-C(4) C-D(1) D-F(7) D-E(3) B-E(6) C-F(5)

סעיף א(1)-(2)

נתון גרף לא מכוון G=(V,E), המיוצג על ידי רשימת הסמיכויות שלפניכם. (1) הפעילו אלגוריתם סריקה לעומק DFS על הגרף הנתון, החל מהקודקוד a. שרטטו במחברתכם את עץ הסריקה DFS שמתקבל. (2) הפעילו אלגוריתם סריקה לרוחב BFS על הגרף הנתון, החל מהקודקוד a. שרטטו במחברתכם את עץ הסריקה BFS שמתקבל.

סעיף ב(1)-(2)

לפניכם גרף לא מכוון ממושקל G. לכל קשת יש משקל חיובי. (1) כתבו את המסלולים הקצרים (הקלים) בגרף G, מקודקוד S לכל אחד מהקודקודים בגרף. אין צורך להציג מעקב. (2) בעבור הגרף G הנתון, שרטטו את עץ המסלולים הקצרים מקודקוד S.

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

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

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

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

דלגו לשאלה דומה ←