דף 1 מתוך 1

2009 מועד א' שאלה 1.א

נשלח: 12:45 26/06/2010
על ידי kes6
משהו כאן חשוד -

בפתרון טוענים שבהרצת DFS, נקבל שני עצים שונים (כתלות באיך מסודרת רשימת השכנויות של X)
אך העצים שהתקבלו הם זהים לגמרי מבחינת מצביעים, ובשניהם רכיב קשירות אחד. ההבדל היחיד הוא איזו צלע תוגדר כ - CROSS, מ - X ל - Y או מ - X ל - Z.
האם לכך הכוונה? האם שני עצים כאלה מוגדרים להיות שונים?

תודה

Re: 2009 מועד א' שאלה 1.א

נשלח: 18:36 26/06/2010
על ידי Shahar
העצים שונים, כי אין להם אותן צלעות.
שתי הרצות:
1. נתחיל מX, נמשיך לV, ואז לZ.
העץ שקבלנו הוא:
x-->v-->z

2. נתחיל מX, נמשיך לZ. נתקענו, אז נחזור לX. עכשיו נלך לV. לא נמשיך לZ כי היינו בו כבר.
העץ שקבלנו הוא:
v<--x-->z