Question

dfs
bfs

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

הסרת צמתי הגרף בזה אחר זה, לפי הסדר, מותירה את שארית הגרף קשיר.

על האלגוריתם לרוץ בסיבוכיות זמן O(V+E)O(|V| + |E|).

1

Answers

פתרון ללא הוכחה:

נריץ BFS ונחזיר את הצמתים בסדר לא עולה של המרחקים שלהם.

אפשרות נוספת:

נריץ DFS ונחזיר את הצמתים בסדר יורד של זמני הנסיגה שלהם.

1
Feedback