מבחן 2002 מועד ב'

מנהל: TA_Isana

מבחן 2002 מועד ב'

הודעהעל ידי michal cohen » 22:51 25/06/2010

שאלה 3 סעיף שני.
למה זה O(v)? הרי זה צריך להיות כמו בDFS רגיל שבמקרה הגרוע מצאנו את המעגל רק בסוף. אז כאילו עברנו על כל הצלעות ועל כל הקדקודים... לא?
michal cohen
 
הודעות: 87
הצטרף: 19:04 11/11/2009

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

הודעהעל ידי בר כהן » 11:24 26/06/2010

לא ממש, האלגוריתם שלהם , בניגוד ל DFS רגיל, ייעצר כאשר הוא יגיע למעגל, כלומר הוא לכל היותר רץ קדימה V|| קודקודים ולכן גם על |V| צלעות.
תחשבי על זה ככה, על קוד קודקוד שהאלגוריתם נכנס אליו, הוא קופץ לקודקוד שכן (כלומר מעבר על צלע אחת) מבלי לבדוק בכלל את שאר השכנים (רקורסיה)
וידוע שיש מעגל, לכן בהכרח במהלך הדרך הוא יסגור מעגל
בר כהן
 
הודעות: 146
הצטרף: 18:24 22/10/2009

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

הודעהעל ידי michal cohen » 11:29 26/06/2010

אתה צודק, אבל מה אם יש כמה רכיבי קשירות?
ז"א אולי עברתי על אלף רכיבי קשירות שאין בהם מעגל ורק בסוף יש מעגל של שלוש צלעות שהוא אפסי לעומת כל שאר קדקודים שעברתי עליהם?
michal cohen
 
הודעות: 87
הצטרף: 19:04 11/11/2009

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

הודעהעל ידי בר כהן » 11:42 26/06/2010

אז? אם עברת על אלף רכיבי קשירות בלי מעגלים, אז עברת עד כה על 1-|V| צלעות לכל היותר בכל הרכיבים יחד.
תחשבי על זה רגע :)
בר כהן
 
הודעות: 146
הצטרף: 18:24 22/10/2009


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

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ו 2 אורחים