۰
subtitle
ارسال: #۱
سوال در مورد الگوریتم BFS
سلام
کدامیک از گزینه های زیر در مرود الگوریتم BFS صحیح نمی باشد؟
۱-با اجرای BFS بر روی گراف جهت دار ممکن است در این گراف ,یال درختی دیده شود.
۲-با اجرای BFS بر روی گراف بدون جهت ممکن نیست در این گراف یال جلو رو دیده شود.
۳-با اجرای BFS بر روی گراف جهت دار ممکن است در این گراف یال جلو رو دیده شود.
۴-با اجرای BFS بر روی گراف بدون جهت ممکن نیست در این گاف یال برگشتی دیده شود
به نظرم همه گزینه ها درسته!
گزینه یک که درسته... گزینه دو و ۴ هم با توجه به اینکه بدون جهت هستن درسته گزینه سه هم با توجه به مثال زیر که پیمایش bfs رو با فلش قرمز مشخص کردم به نظرم درسته !
ولی در پاسخ گفته شده گزینه ۳ جوابه یعنی صحیح نیست
![[تصویر: 237659_Photo0182.jpg]](https://img.manesht.ir/237659_Photo0182.jpg)
لطفا" بگید کجا اشتباه کردم ؟!!
کدامیک از گزینه های زیر در مرود الگوریتم BFS صحیح نمی باشد؟
۱-با اجرای BFS بر روی گراف جهت دار ممکن است در این گراف ,یال درختی دیده شود.
۲-با اجرای BFS بر روی گراف بدون جهت ممکن نیست در این گراف یال جلو رو دیده شود.
۳-با اجرای BFS بر روی گراف جهت دار ممکن است در این گراف یال جلو رو دیده شود.
۴-با اجرای BFS بر روی گراف بدون جهت ممکن نیست در این گاف یال برگشتی دیده شود
به نظرم همه گزینه ها درسته!
گزینه یک که درسته... گزینه دو و ۴ هم با توجه به اینکه بدون جهت هستن درسته گزینه سه هم با توجه به مثال زیر که پیمایش bfs رو با فلش قرمز مشخص کردم به نظرم درسته !
ولی در پاسخ گفته شده گزینه ۳ جوابه یعنی صحیح نیست
لطفا" بگید کجا اشتباه کردم ؟!!
۰
ارسال: #۲
RE: سوال در مورد الگوریتم BFS
(۲۶ دى ۱۳۹۲ ۰۴:۱۵ ب.ظ)tabassomesayna نوشته شده توسط: سلام
کدامیک از گزینه های زیر در مرود الگوریتم BFS صحیح نمی باشد؟
۱-با اجرای BFS بر روی گراف جهت دار ممکن است در این گراف ,یال درختی دیده شود.
۲-با اجرای BFS بر روی گراف بدون جهت ممکن نیست در این گراف یال جلو رو دیده شود.
۳-با اجرای BFS بر روی گراف جهت دار ممکن است در این گراف یال جلو رو دیده شود.
۴-با اجرای BFS بر روی گراف بدون جهت ممکن نیست در این گاف یال برگشتی دیده شود
به نظرم همه گزینه ها درسته!
گزینه یک که درسته... گزینه دو و ۴ هم با توجه به اینکه بدون جهت هستن درسته گزینه سه هم با توجه به مثال زیر که پیمایش bfs رو با فلش قرمز مشخص کردم به نظرم درسته !
ولی در پاسخ گفته شده گزینه ۳ جوابه یعنی صحیح نیست
لطفا" بگید کجا اشتباه کردم ؟!!
توی پیمایش BFS هیچوقت یال جلورو نداریم، چون اگه یالی وجود داشته باشه، حتما تو پیمایش از اون استفاده می کنیم! با توجه به تعریف یال جلورو که یال از یک نود به نود در زیر درخت اون نود.
از اونجا که یال جلورو و یال برگشتی تو گراف بدون جهت یکی هست، پس یال برگشتی هم نداریم، که درستی گزینه ۴
ارسال: #۳
RE: سوال در مورد الگوریتم BFS
(۲۶ دى ۱۳۹۲ ۰۸:۴۵ ب.ظ)minami نوشته شده توسط:(26 دى ۱۳۹۲ ۰۴:۱۵ ب.ظ)tabassomesayna نوشته شده توسط: سلام
کدامیک از گزینه های زیر در مرود الگوریتم BFS صحیح نمی باشد؟
۱-با اجرای BFS بر روی گراف جهت دار ممکن است در این گراف ,یال درختی دیده شود.
۲-با اجرای BFS بر روی گراف بدون جهت ممکن نیست در این گراف یال جلو رو دیده شود.
۳-با اجرای BFS بر روی گراف جهت دار ممکن است در این گراف یال جلو رو دیده شود.
۴-با اجرای BFS بر روی گراف بدون جهت ممکن نیست در این گاف یال برگشتی دیده شود
به نظرم همه گزینه ها درسته!
گزینه یک که درسته... گزینه دو و ۴ هم با توجه به اینکه بدون جهت هستن درسته گزینه سه هم با توجه به مثال زیر که پیمایش bfs رو با فلش قرمز مشخص کردم به نظرم درسته !
ولی در پاسخ گفته شده گزینه ۳ جوابه یعنی صحیح نیست
لطفا" بگید کجا اشتباه کردم ؟!!
توی پیمایش BFS هیچوقت یال جلورو نداریم، چون اگه یالی وجود داشته باشه، حتما تو پیمایش از اون استفاده می کنیم! با توجه به تعریف یال جلورو که یال از یک نود به نود در زیر درخت اون نود.
از اونجا که یال جلورو و یال برگشتی تو گراف بدون جهت یکی هست، پس یال برگشتی هم نداریم، که درستی گزینه ۴
بله بله انگار اشتباه کردم..
اصلا" در این شکلی که کشیدم یال جلو رو نداریم من یه لحظه حواسم به تعریف یال جلو رو نبود
ممنونم
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close