(۲۶ دى ۱۳۹۲ ۰۴:۱۵ ب.ظ)tabassomesayna نوشته شده توسط:  سلام
کدامیک از گزینه های زیر در مرود الگوریتم BFS صحیح نمی باشد؟
۱-با اجرای BFS بر روی گراف جهت دار ممکن است در این گراف ,یال درختی دیده شود.
۲-با اجرای BFS بر روی گراف بدون جهت ممکن نیست در این گراف یال جلو رو دیده شود.
۳-با اجرای BFS بر روی گراف جهت دار ممکن است در این گراف یال جلو رو دیده شود.
۴-با اجرای BFS بر روی گراف بدون جهت ممکن نیست در این گاف یال برگشتی دیده شود

به نظرم همه گزینه ها درسته!
گزینه یک که درسته... گزینه دو و ۴ هم با توجه به اینکه بدون جهت هستن درسته گزینه سه هم با توجه به مثال زیر که پیمایش bfs رو با فلش قرمز مشخص کردم به نظرم درسته !
ولی در پاسخ گفته شده گزینه ۳ جوابه یعنی صحیح نیست

لطفا" بگید کجا اشتباه کردم ؟!!

(۲۶ دى ۱۳۹۲ ۰۸:۴۵ ب.ظ)minami نوشته شده توسط:  

(26 دى ۱۳۹۲ ۰۴:۱۵ ب.ظ)tabassomesayna نوشته شده توسط:  سلام
کدامیک از گزینه های زیر در مرود الگوریتم BFS صحیح نمی باشد؟
۱-با اجرای BFS بر روی گراف جهت دار ممکن است در این گراف ,یال درختی دیده شود.
۲-با اجرای BFS بر روی گراف بدون جهت ممکن نیست در این گراف یال جلو رو دیده شود.
۳-با اجرای BFS بر روی گراف جهت دار ممکن است در این گراف یال جلو رو دیده شود.
۴-با اجرای BFS بر روی گراف بدون جهت ممکن نیست در این گاف یال برگشتی دیده شود

به نظرم همه گزینه ها درسته!
گزینه یک که درسته... گزینه دو و ۴ هم با توجه به اینکه بدون جهت هستن درسته گزینه سه هم با توجه به مثال زیر که پیمایش bfs رو با فلش قرمز مشخص کردم به نظرم درسته !
ولی در پاسخ گفته شده گزینه ۳ جوابه یعنی صحیح نیست

لطفا" بگید کجا اشتباه کردم ؟!!

توی پیمایش BFS هیچوقت یال جلورو نداریم، چون اگه یالی وجود داشته باشه، حتما تو پیمایش از اون استفاده می کنیم! با توجه به تعریف یال جلورو که یال از یک نود به نود در زیر درخت اون نود.

از اونجا که یال جلورو و یال برگشتی تو گراف بدون جهت یکی هست، پس یال برگشتی هم نداریم، که درستی گزینه ۴