גרף לא מכוון G=(V,E), רשימת סמיכויות
גרף לא מכוון G=(V,E), רשימת סמיכויות
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
קשתות (משקל): 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) E-F(בשרטוט לא מופיע משקל לקשת זו)
סעיף א(1)-(2)
נתון גרף לא מכוון G=(V,E), המיוצג על ידי רשימת הסמיכויות שלפניכם. (1) הפעילו אלגוריתם סריקה לעומק DFS על הגרף הנתון, החל מהקודקוד a. שרטטו במחברתכם את עץ הסריקה DFS שמתקבל. (2) הפעילו אלגוריתם סריקה לרוחב BFS על הגרף הנתון, החל מהקודקוד a. שרטטו במחברתכם את עץ הסריקה BFS שמתקבל.
סעיף ב(1)-(2)
לפניכם גרף לא מכוון ממושקל G. לכל קשת יש משקל חיובי. (1) כתבו את המסלולים הקצרים (הקלים) בגרף G, מקודקוד S לכל אחד מהקודקודים בגרף. אין צורך להציג מעקב. (2) בעבור הגרף G הנתון, שרטטו את עץ המסלולים הקצרים מקודקוד S.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.