سلام
در پیمایش DFS این گراف چرا یال Z--->X , یال Cross هست ؟ چرا backward edge نیست ؟؟؟
[attachment=15132]
یال بازگشتی یعنی به یکی از اجدادش متصل است در حالی که تو این سوال هیچ کدوم جد اون یکی نیست پس cross هست(dfs از s شروع میشه)
مگه با dfs نباید درخت ایجاد کنیم؟ چرا تو این سؤال رأس v رو به s وصل نکرده ؟ این طوری که جنگل داریم!
(۱۲ بهمن ۱۳۹۲ ۰۸:۰۶ ب.ظ)minami نوشته شده توسط: مگه با dfs نباید درخت ایجاد کنیم؟ چرا تو این سؤال رأس v رو به s وصل نکرده ؟ این طوری که جنگل داریم!
dfs ضرورتا درخت نمی سازه ممکنه جواب جنگل باشه
(۱۲ بهمن ۱۳۹۲ ۰۹:۲۶ ب.ظ)izadan11 نوشته شده توسط:(12 بهمن ۱۳۹۲ ۰۸:۰۶ ب.ظ)minami نوشته شده توسط: مگه با dfs نباید درخت ایجاد کنیم؟ چرا تو این سؤال رأس v رو به s وصل نکرده ؟ این طوری که جنگل داریم!
dfs ضرورتا درخت نمی سازه ممکنه جواب جنگل باشه
ممنون، متوجه مشکلم شدم.
(۱۲ بهمن ۱۳۹۲ ۰۷:۳۱ ب.ظ)izadan11 نوشته شده توسط: یال بازگشتی یعنی به یکی از اجدادش متصل است در حالی که تو این سوال هیچ کدوم جد اون یکی نیست پس cross هست(dfs از s شروع میشه)
دادا اگه از S شروع کنیم همون اول بریم به z که دیگه یاله zx میشه forward
نظرت چیه؟
(۱۴ بهمن ۱۳۹۲ ۱۰:۲۳ ب.ظ)hosshah نوشته شده توسط:(12 بهمن ۱۳۹۲ ۰۷:۳۱ ب.ظ)izadan11 نوشته شده توسط: یال بازگشتی یعنی به یکی از اجدادش متصل است در حالی که تو این سوال هیچ کدوم جد اون یکی نیست پس cross هست(dfs از s شروع میشه)
دادا اگه از S شروع کنیم همون اول بریم به z که دیگه یاله zx میشه forward
نظرت چیه؟
باید به ترتیب حروف الفبا پیش رفت
(۱۵ بهمن ۱۳۹۲ ۱۲:۴۷ ق.ظ)izadan11 نوشته شده توسط: باید به ترتیب حروف الفبا پیش رفت
آها پس همه این فرض ها هم روش بوده
تشکر