سلام
سوال ۴۸ طراحی الگوریتم کنکور فناوری اطلاعات سال ۸۶ هست
یه توضیح مختصر لطفا درباره اینکه چرا جواب میشه گزینه ۴ بهم بدین لطفا
چرا جواب گزینه ۲ نمیشه!؟ فرقشون چیه مگه
سلام وقت بخیر.
اگه قرار باشه کمترین تعداد یال رو داشته باشه و وزنشون اهمیت نداشته باشه، من BFS رو انتخاب میکنم. چون پیچیدگی محاسباتیش کمتره. دقیقاً هم برای همین کار طراحی شده. دایکسرا مجموع وزن رو در حالتی که تمام وزنها نامنفی باشن کمینه میکنه.
سلام
kruskal برای یافتن درخت پوشای مینیمم استفاده می شود. dijkstra برای یافتن کوتاه ترین مسیر های هم مبدا. dfs , bfs جز الگوریتم های پیمایش گراف هستند.فرق بین دایجسترا با اول سطح اینه که اگر وزن تمام یال ها یکسان باشند دایجسترا به اول سطح تبدیل می شود البته در حاصل نهایی ولی با مرتبه ها و مکانیسم متفاوت. در کل زمانی که کوتاه ترین مسیر ها هم مبدا در گراف با وزن های یکسان یا در گراف بدون وزن را بخواهند از اول سطح استفاده می شود.
در bfs از یک راس شروع و هربار فرزندان ان با یک اولویت از قبل تعیین شده وارد صف می شود و هر باراز صف یک نود برداشته وتکرار مراحل.
در دایجسترا هم از یک صف اولویت استفاده می شود که ابتدا تمام نود ها در ان با یک ارزش زیاد(فاصله از مبدا) قرار دارندبه جز نود مبدا با ارزش صفر هر بار نود با ارزش مینیمم از صف خارج و روی فرزندان ان عمل relax( بررسی اینکه ایا فاصله فعلی بدست امده از فاصله قبلی کمتر است یا نه و در صورت نیاز اصلاح ارزش در صف) انجام می شود .حال اگر ورن تمام یال ها یکسان باشد عمل relax فقط یکبار برای هر نود باعث تغییر ارزش در صف می شود یعنی همان نردیک ترین فاصله جایگزین ارزش اولیه بسیار زیاد می شود.
البته در این تست که فاصله برحست کمترین تعداد یال را می خواهد که از اول سطح استفاده می شود.
BFS کابردش اینه که کوتاه ترین مسیرهایی رو که از یک مبدا یکسان سرچشمه گرفتن رو بر حسب کوتاه ترین یال شناسایی کنه.
کروسکال به همراه پریم (که اینجا تو گزینه ها نیست) واسه پیدا کردن درخت پوشای کمینه هستن.
دایکسترا هم واسه SSSP هستش . منظور از SSSP کوتاه ترین مسیر وزن دار از یک راس هستش. single-source shortest-path
مساله ای که اینجا عرض میکنم این هستش : تو صورت سوال اشاره شده و به محض دیدن این تیپ تست های میشه جواب داد " مسیر ساده با کمترین تعداد یال " هستش. که DFS و BFS الگوریتم هایی برای پیمایش ساده گراف هستند.
سلام
از توضیح تک ب تک دوستان ممنونم
از هر کدوم یه چیزی یاد گرفتم عالی بود
دروود فراوان