מציאת נגישות ב DFS
אנונימי (guest) 27 Jan 2011 09:27
שאלה בקשר לנגישות צמתים ע"י הפעלת DFS. הדרך להראות שצומת x נגיש מצומת y זה לבדוק שזמן הגישה ל x קטן מזמן היציאה ל y ?
ושאלה נוספת, אם אנחנו רוצים לבדוק ששני צמתים הם באותו רכיב קשירות בגרף לא מכוון, זמן הריצה לזה הוא לא אקרמן הפוך? כי מסתמן שרוצים להגיד לינארי אבל הדרך לבדוק היא לטפס על העץ ולחפש אב משותף, וזה לא בדיוק לינארי.
הערה: נסיתי לכתוב מימין לשמאל, מקווה שעבד…
הערה (ר.): לא, אבל תיקנתי.