تالار گفتمان مانشت
روش بدست آوردن یال های پیش رو ،پسین ،صلیبی(طراحی الگوریتم) - نسخه‌ی قابل چاپ

روش بدست آوردن یال های پیش رو ،پسین ،صلیبی(طراحی الگوریتم) - tarane1992 - 09 آذر ۱۳۹۲ ۱۱:۲۸ ق.ظ

سلام

دوستان کسی میتونه راه بدست آوردن این یالهارو برام تک تک توضیح بده چطوریه ؟؟Blush

سوالو در پایین گذاشتم رو همون توضیح بدید ممنون میشم.یه راهی که بتونم این گونه تست هارو بزنم.


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


RE: روش بدست آوردن یال های پیش رو ،پسین ،صلیبی(طراحی الگوریتم) - rad.bahar - 09 آذر ۱۳۹۲ ۰۲:۴۵ ب.ظ

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

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

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

RE: روش بدست آوردن یال های پیش رو ،پسین ،صلیبی(طراحی الگوریتم) - tarane1992 - 09 آذر ۱۳۹۲ ۰۸:۲۴ ب.ظ

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

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

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


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


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

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

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

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

RE: روش بدست آوردن یال های پیش رو ،پسین ،صلیبی(طراحی الگوریتم) - tarane1992 - 09 آذر ۱۳۹۲ ۰۹:۳۳ ب.ظ

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

RE: روش بدست آوردن یال های پیش رو ،پسین ،صلیبی(طراحی الگوریتم) - rad.bahar - 09 آذر ۱۳۹۲ ۱۱:۰۰ ب.ظ

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



خوب در این سوال ما میتونیم از 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 جهت دار ما یال عقب رو(پسین) نداریم. خوب در اینجا ما یال صلیبی هم نداریم و جواب که گفته ۴ به نظر من درست نیست جوابش تو گزینه ها نیست.HuhHuhHuhHuhHuhHuh
از روی همین صورت سوال مشخص هست که این حرف که در پیمایش dfs جهت دار ما یال عقب رو(پسین) نداریم اشتباه است.
تا انجایی من می دانم در پیمایش bfs در گراف جهت دار یال های پیش رو وجود ندارند.

RE: روش بدست آوردن یال های پیش رو ،پسین ،صلیبی(طراحی الگوریتم) - tarane1992 - 10 آذر ۱۳۹۲ ۱۲:۱۴ ق.ظ

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

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

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

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

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

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