נתון גרף G(V,E) לא מכוון ולא משוקלל, ללא קשר עצמי (self-loop), שבו n קודקודים ממוספרים מ-v0 עד v(n-1).
נתון גרף G(V,E) לא מכוון ולא משוקלל, ללא קשר עצמי (self-loop), שבו n קודקודים ממוספרים מ-v0 עד v(n-1).
הגרף לדוגמה: שלושה רכיבי קשירות נפרדים - {1,5} (קשת יחידה), {2,4,8} (משולש), ו-{0,3,6,7,9} (חמישה קודקודים מחוברים).
רכיב 1: (5)---(1)
רכיב 2: (2)---(8)
\ /
(4)
רכיב 3: (3)
|
(7)
/ \
(9)---(0)
|
(6)
כתבו אלגוריתם שבו לכל קודקוד vj בגרף, מוצא ומחזיר את כל הקודקודים שיש מסלול בין קודקוד vj (הנתון) וביניהם. הערה: יש לכתוב אלגוריתם יעיל שאינו עובר על כל המסלולים האפשריים. דוגמה: עבור הגרף שלפניכם וקודקוד 3, האלגוריתם יחזיר את הקודקודים 0, 6, 7, 9.
'רכיב קשירות' בגרף G(V,E) לא מכוון הוא קבוצת קודקודים שבה בין כל שני קודקודים בקבוצה יש מסלול, ואין שום קודקוד היוצאת מקודקוד לקבוצה לקודקוד שאינו בקבוצה. קודקוד שאין בינו ובין שום קודקוד אחר בקבוצה קשת, נחשב רכיב קשירות בפני עצמו. כתבו אלגוריתם המוצא ומחזיר את רכיב הקשירות הקטן ביותר (כלומר את הקבוצה שבה המספר המינימלי של קודקודים) בגרף G(V,E). למשל עבור הדוגמה שלעיל, האלגוריתם יחזיר את הקודקודים 5, 1. הניחו שיש רק רכיב קשירות אחד שהוא הקטן ביותר. הערה: יש לכתוב אלגוריתם יעיל שאינו עובר על כל המסלולים האפשריים.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.