سلام
بچه ها این سوال که میاد درخت فراگیرBFSیاDFSی گرافو میده میگه بین کدوم راسها تو گرافش یال وجود داشته،چجوری میتونیم تشخیص بدیم؟؟
یکی میتونه رو این سوال توضیح بده؟
ممنون.
[attachment=17365]
سلام
میشه از روش حذف گزینه ها استفاده کرد. بین دو راس ۵ و۲ نمیتونه یالی باشه چو ن در غیر این صورت توی پیمایش dfs پس از ملاقات راس۲ ، راس ۵ هم ملاقات میشد یعنی توی درختمون از ۲ به ۵ یال د اشتیم ولی الان از ۱ یه ۵ یال داریم خب پس گزینه ۱ غلطه.
برای دو راس ۶ و۲ و همین طور ۶ و ۷ هم به همین شکل میتوان استدلال کرد . اما گزینه ۳ بین دو راس ۱ و۴ میتونه یه یال باشه .حالا شاید بپرسید پس چرا بعد از ۱ راس ۴ را ندیده (اگه میتونه یالی باشه)؟ جواب این است که این روش هم ممکنه و همان طور که میدونید درخت dfs منحصر به فرد نیست.