מבחן 2002 מועד ב'

מנהל: TA_Isana

שלח תגובה
michal cohen
הודעות: 87
הצטרף: 19:04 11/11/2009

מבחן 2002 מועד ב'

שליחה על ידי michal cohen » 23:51 25/06/2010

שאלה 3 סעיף שני.
למה זה O(v)? הרי זה צריך להיות כמו בDFS רגיל שבמקרה הגרוע מצאנו את המעגל רק בסוף. אז כאילו עברנו על כל הצלעות ועל כל הקדקודים... לא?

בר כהן
הודעות: 146
הצטרף: 18:24 22/10/2009

Re: מבחן 2002 מועד ב'

שליחה על ידי בר כהן » 12:24 26/06/2010

לא ממש, האלגוריתם שלהם , בניגוד ל DFS רגיל, ייעצר כאשר הוא יגיע למעגל, כלומר הוא לכל היותר רץ קדימה V|| קודקודים ולכן גם על |V| צלעות.
תחשבי על זה ככה, על קוד קודקוד שהאלגוריתם נכנס אליו, הוא קופץ לקודקוד שכן (כלומר מעבר על צלע אחת) מבלי לבדוק בכלל את שאר השכנים (רקורסיה)
וידוע שיש מעגל, לכן בהכרח במהלך הדרך הוא יסגור מעגל

michal cohen
הודעות: 87
הצטרף: 19:04 11/11/2009

Re: מבחן 2002 מועד ב'

שליחה על ידי michal cohen » 12:29 26/06/2010

אתה צודק, אבל מה אם יש כמה רכיבי קשירות?
ז"א אולי עברתי על אלף רכיבי קשירות שאין בהם מעגל ורק בסוף יש מעגל של שלוש צלעות שהוא אפסי לעומת כל שאר קדקודים שעברתי עליהם?

בר כהן
הודעות: 146
הצטרף: 18:24 22/10/2009

Re: מבחן 2002 מועד ב'

שליחה על ידי בר כהן » 12:42 26/06/2010

אז? אם עברת על אלף רכיבי קשירות בלי מעגלים, אז עברת עד כה על 1-|V| צלעות לכל היותר בכל הרכיבים יחד.
תחשבי על זה רגע :)

שלח תגובה

חזור אל “- מבני נתונים 2010”