جدا " عجب اشتباهی میکردم . خیلی کمک بزرگی بهم کردید

یعنی یال های صلیبی و پیش رو و پس رو از گراف اصلی بدست می آیند ولی یال درختی از درخت.

آره منم خوندم در bfs جهت دار پش رو نداریم.

بسیار ممنونم از شما.ممنون که اشتباه بزرگمو بهم فهموندید

موفق باشیدو سلامت

ان شالله بتونیم باز از علم شما بهره مند بشیم.

به این لینک نگاه کنید امیدوارم مفید واقع بشه البته در کتاب clrs در بخش گراف در پیمایش DFS در زیر عنوانی به نام طبقه بندی یال ها این موضوع را توضیح داده

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

فکر کنم جواب گ ۴ باشه درسته؟

آره یادم رفت گزینه درستو بنویسم جواب گزینه ۴ درسته.

---

خوب ببینید من یال صلیبی و یال درختی رو متوجه میشم.ولی پسرو و پیش رو نمیفهمم.

خوب من را ه حل حل شدشو گذاشتم در لینک زیر :


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


خوب وقتی گرافو با dfs پیمایش کردیمو درختمون ساختیم بخواییم گره پیش رو و پس رو مشخص کنیم چرا در این شکل فقط یک پیش رو و یک پس رو داریم مگه تعریف پیش رو این نیست که"یال پیشرو یالی هست که از جد یک گره به گره های نواده کشیده میشه."
و یال پس رو "یال عقب رو یالی هست که از یک فرزند به پدر بزرگش برگشته"

خوب در این سوال ما میتونیم از b به d یا e به c یا d به a یال عقب رو داشته باشیم چرا این سوال فقط e به c رو یال عقب رو در نظر گرفته و ما فقط همین یک یال عقبرو رو داریم ؟؟من چه چیزی رو اشتباه میکنم؟؟

یال پیش یعنی ازپدبزرگ به فرزندان یال در نظر بگیریم پس میشه a بهd و a به e و a به b چرا پس جوابش فقط a به e هست؟؟

میشه کمی توضیح بدید من مشکل کارم چیه و چه چیزی رو دارم اشتباه میکنم؟؟

(۰۹ آذر ۱۳۹۲ ۰۸:۲۴ ب.ظ)tarane1992 نوشته شده توسط:  آره یادم رفت گزینه درستو بنویسم جواب گزینه ۴ درسته.

---

خوب در این سوال ما میتونیم از b به d یا e به c یا d به a یال عقب رو داشته باشیم چرا این سوال فقط e به c رو یال عقب رو در نظر گرفته و ما فقط همین یک یال عقبرو رو داریم ؟؟من چه چیزی رو اشتباه میکنم؟؟

یال پیش یعنی ازپدبزرگ به فرزندان یال در نظر بگیریم پس میشه a بهd و a به e و a به b چرا پس جوابش فقط a به e هست؟؟

دقت کنید که یال پیش رو و پس رو به گراف اصلی تعلق دارند و در گراف درخت bfs وجود ندارند در گراف اصلی هیچ یالی از b به d یا d به a وجود نداره ولی در گراف اصلی از e به c یال وجود داره پس این یال عقب رو هست. در گراف اصلی هیچ یالی از a بهd و a به b وجود نداره ولی در گراف اصلی از a به e یال وجود داره پس این یال پیش رو هست.

---

(۰۹ آذر ۱۳۹۲ ۰۹:۳۳ ب.ظ)tarane1992 نوشته شده توسط:  من خودم تو کتاب طراحی خوندم در پیمایش dfs جهت دار ما یال عقب رو(پسین) نداریم. خوب در اینجا ما یال صلیبی هم نداریم و جواب که گفته ۴ به نظر من درست نیست جوابش تو گزینه ها نیست.

از روی همین صورت سوال مشخص هست که این حرف که در پیمایش dfs جهت دار ما یال عقب رو(پسین) نداریم اشتباه است.
تا انجایی من می دانم در پیمایش bfs در گراف جهت دار یال های پیش رو وجود ندارند.

من خودم تو کتاب طراحی خوندم در پیمایش dfs جهت دار ما یال عقب رو(پسین) نداریم. خوب در اینجا ما یال صلیبی هم نداریم و جواب که گفته ۴ به نظر من درست نیست جوابش تو گزینه ها نیست.