دوستان سلام . این سوال سال گذشته IT هست که سنجش گزینه ۱ رو زده ولی پارسه میگه میشه گزینه ۳////
میشه کسی کامل توضیح بده که چطور با الگوریتم bfs و dfs "طول دور" حساب میشه ؟ خواهش میکنم توضیح پارسه رو کپی نکنید چون خوندمش ولی متوجه نشدم
![[تصویر: 246632_alg.png]](https://img.manesht.ir/246632_alg.png)
سلام
سوال شما رو چون واسه خودمم شک ایجاد شده بود همین الان از دکتر یوسفی از طریق تلفن پرسیدم
جوابشو واستون می نویسم:
در گراف غیرجهت دار یا یال treeedge وجود داره یا cross edge حالا اگر همه tree یاشن که درخت دور نداشته!اگه هم crossedge داشته باشه یعنی دور داشته حالا اگر این دور در دو گره غیر هم شماره به وجود بیاد یعنی دور با طول زوج( یعنی یه گره شمارش فرد یه گره هم شمارش زوج باشه!)
سر کلاس واسمون دکتر مثال زدن. اینو که گفتن یادم اومد حالا شما هم یه مثال بزنید واسه خودتون متوجه اصل فضیه می شید..
موفق باشید...
اگر گراف هم همبند باشه میشه با یه بار بی اف اس زدن این دور متوجش شد
این طور که یک سطح درمیون به فرزندان هر سطحی که داریم بچههاش تولید میکنیم مقدار ۰ و یک بدی بعد وقتی یال کراس دیدی چک کنی دوسر یالت دو تا ۰(دو تا ۱) هست یا نه یک سر ۰ یک سر دیگه ۱ هست اگر دو سر یال متفاوت بود دورت زوجه اگه شبیه بود فرده
اگر همبند نباشه این کار باید n بار بی اف اس زدن انجام بدی
ممنونم از توضیحتون دوستان. پس با این حساب سازمان سنجش گزینه غلط رو انتخاب کرده و در نهایت n بار bfs درست میشه ،چون در واقع به ما نگفته گزاف همبنده یا ناهمبند پس باید حالت بدتر رو در نظر بگیریم...درست میگم؟
یه سوال دیگم هم اینه که ایا با dfs هم میشه طول دور رو حساب کرد؟ و اگر بله از نظر مرتبه زمانی چه فرقی با راه قبلی داره؟
کسی نبووود جواب بده راجع به dfs ؟؟؟؟؟؟؟؟
(۱۸ بهمن ۱۳۹۲ ۰۳:۰۴ ب.ظ)m_ok نوشته شده توسط: کسی نبووود جواب بده راجع به dfs ؟؟؟؟؟؟؟؟
شرط لازم و کافی برای وجود سیکل در DFS آن است که پیمایش یال بک داشته باشد(چون که رفتیم در واقع یک سری node را دیدیم حالا اگر Back یعنی سیکل وجود دارد.)
در پیمایش DFS گراف غیر جهت دار Forward و Cross وجود ندارد چون Back در نظر گرفته می شه برای غیر جهت دارها و Cross وجود ندارد زیرا اگر که بود برنمی گشتیم و حالت tree پیمایش نمی شد!
ولی برای پیدا کردن دور با طول زوج BFSبهتر و قطعی تر می تواند جواب دهد!
ممنون دوست عزیز . من بیشتر مد نظرم "طول" دور بود که چطوری تو DFS بدست میاد...در مورد شرط وجود یال پسین اطلاع دارم
بچه ها من این سوالو مشکل دارم یکی کامل توضیح بده لطفا
(۱۶ بهمن ۱۳۹۲ ۰۹:۳۹ ب.ظ)mahsalove نوشته شده توسط: سلام
سوال شما رو چون واسه خودمم شک ایجاد شده بود همین الان از دکتر یوسفی از طریق تلفن پرسیدم
جوابشو واستون می نویسم:
در گراف غیرجهت دار یا یال treeedge وجود داره یا cross edge حالا اگر همه tree یاشن که درخت دور نداشته!اگه هم crossedge داشته باشه یعنی دور داشته حالا اگر این دور در دو گره غیر هم شماره به وجود بیاد یعنی دور با طول زوج( یعنی یه گره شمارش فرد یه گره هم شمارش زوج باشه!)
سر کلاس واسمون دکتر مثال زدن. اینو که گفتن یادم اومد حالا شما هم یه مثال بزنید واسه خودتون متوجه اصل فضیه می شید..
موفق باشید...
این غلطه ... مثال نقض داره ...
(۰۲ بهمن ۱۳۹۳ ۱۲:۵۸ ق.ظ)Densike نوشته شده توسط:سلام(16 بهمن ۱۳۹۲ ۰۹:۳۹ ب.ظ)mahsalove نوشته شده توسط:
این غلطه ... مثال نقض داره ...
میشه لطف کنید الگوریتمشو توضیح بدین.
خیلی ممنون
جواب این سوال همون n بار BFS هست که سنجش گفته
ببینید روش حل این سوال همونی هست که گفته شد ، یعنی ما BFS میزنیم ، هرجا به یک راس خاکستری رسیدیم فاصله هاشون رو نگاه میکنیم و اگر یکی فرد دیگری زوج یعنی دور به طول زوج داریم ، ولی این الگوریتم شرط موفقیتش اینه که راس شروع ما یکی از راس های شرکت کننده در دور باشه ، باور ندارید ؟ این مثالی که میگم،رو بزنید ：
یه مربع رسم کنید ، حالا یک راس دیگه خارج از مربع رسم کنید و به ۴ راس مربع وصل کنید ، حالا اگر این راس به عنوان راس شروع،باشه این BFS دور مربع ما،رو شناسایی نمیکنه ... ولی اگر از یکی از ریوس مربع شروع کنیم دور شناسایی میشه
پس ما به n بار bfs احتیاج داریم که مطمئن شیم