(۰۴ اسفند ۱۳۹۱ ۱۲:۰۶ ق.ظ)مطهره نوشته شده توسط: برای سوال ۴۳ نظرتون درمورد این گراف چیه؟
گراف رو در تصویر میذارم
توضیح: فرض کنید شروع الگوریتم bfs از نقطه a باشد. بعد ان b و c ملاقات خواهند شد.و بعد e و d . بعد از d الگوریتم تمام می شود و دوری به طول فرد پیدا می شود. حالا اگر الگوریتم را دوباره انجام دهیم از راس b، بعد ان a و e و همین طور تاآخر ، باز هم با اتمام الگوریتم دوری به طول فرد پیدا می شود. کلا می خوام بگم با یکبار انجام bfs نمی توان دوری به طول زوج پیدا کرد. و از آنجا که یکی از کاربردهای dfs در پیدا کردن دور است، با انجام آن سریعتر می توان دور را پیدا کرد.
ضمنا نیاز به نرم افزار نیست. با پینت هم می توان شکل کشید
اگر نظری دارید بفرمایید
شما اشتباه حساب کردید برای شکل شما مرحله به مرحله حساب کردم کاملا درسته برای دور abedc مقدار ۲+۳=۵ رو بدست اورده (مقدار اصلی گره d ،۲ هست و مقداری که گره e برای d محاسبه میکند ۳ هست )که نشون میده این دور فرده و برای دور abec مقدار ۳+۱=۴ رو بدست اورده (مقدار اصلی گره c ،۱ هست و مقداری که گره e برای c محاسبه میکند ۳ هست )که نشون میده این دور به طول زوجه در ضمن در این مثال خاص مقدار محاسبه شده با طول دور برابره
درخت bfs رو همراه با شماره هر گره (ارتفاع اون گره در درخت) و مقدار گره رو برای شما رسم میکنم بررسی کنید
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
در ضمن میان دو راه حل داده شده اولویت با راه حلی هست که از نطر زمانی بهینه تر باشه طبق نکته زیر که از جزوه طراحی الگوریتم قلی زاده هست از نطر زمانی bfs از dfs بهتر هست چون bfs تمام گرههای گراف رو یکبار و هر یال اون رو حداکثر یکبار پیمایش میکنه یعنی ممکنه یالی رو اصلا مشاهده نکنه ولی dfs تمام تمام گرههای گراف رو یکبار و هر یال اون رو حداقل یکبار پیمایش میکنه که زمان بیشتری میبره
برای شکل زیر dfs چطور عمل میکنه اگر عمق گره b یک مقدار خیلی بزرگی مثل بی نهایت باشه ؟
در شکلهایی شبیه این bfs خیلی بهتر و سریعتر عمل میکنه
اگر الگوریتم bfs در کتاب CLRS رو دیده باشی هنگام مشاهده گره خاکستری در پیمایش یک گره ،دور تشخیص داده می شود