כתבו אלגוריתם המוצא ומחזיר את כל הקודקודים שיש מסלול בינם לבין קודקוד נתון v_j.

⚠ הערה — אילוץ מחייב

יש לכתוב אלגוריתם יעיל שאינו עובר על כל המסלולים האפשריים.

✎ דוגמה

בעבור הגרף שלעיל, וקודקוד 3, האלגוריתם יחזיר את הקודקודים 0, 6, 7, 9.

הסבר: קיים מסלול בין הקודקוד 3 ובין הקודקודים 0, 6, 7, 9.

"רכיב קשירות" בגרף לא מכוון G(V,E) הוא קבוצת קודקודים שבה בין כל שני קודקודים יש מסלול, ואין שום קשת היוצאת מקודקוד בקבוצה לקודקוד שאינו בקבוצה. קודקוד שאין קשת בינו ובין שום קודקוד אחר יהיה בקבוצה משלו.

כתבו אלגוריתם המוצא ומחזיר את רכיב הקשירות הקטן ביותר (כלומר את הקבוצה שבה המספר המינימלי של קודקודים) בגרף G(V,E).

הניחו שיש רק רכיב קשירות אחד שהוא הקטן ביותר.

⚠ הערה — אילוץ מחייב

יש לכתוב אלגוריתם יעיל שאינו עובר על כל המסלולים האפשריים.

✎ דוגמה

בעבור הגרף שלעיל, שלושת רכיבי הקשירות מסומנים בקו מקווקו:

והאלגוריתם יחזיר את הקודקודים 1, 5.