دوستان کسی میدونه در چه مواقعی از DFS و در چه مواقعی از BFS استفاده می شه؟
و اینکه اگر وزن همه یالهای گراف یکسان باشه کدوم پیمایش بهتره؟ چرا؟
اگر گراف با وزن منفی داشته باشیم چی؟
مرسی
اگر وزن همه یالها یکسان باشه BFS بهتره . وقتی عمق گراف زیاد باشه BFS بهتره دیگه!!
در گراف های بدون وزن( یا گرافی که تمام یالها وزن واحدی دارند )از جستجوی BFS استفاده می شود
البته در مورد یافتن درخت پوشای پرایم،
در الگوریتم دایکسترا
و برای یافتن کوتاهترین مسیر ار یک راس به راس دیگر هم از این جستجو استفاده می شود
(۲۵ بهمن ۱۳۹۰ ۰۴:۵۷ ب.ظ)پشتکار نوشته شده توسط: دوستان کسی میدونه در چه مواقعی از DFS و در چه مواقعی از BFS استفاده می شه؟
و اینکه اگر وزن همه یالهای گراف یکسان باشه کدوم پیمایش بهتره؟ چرا؟
اگر گراف با وزن منفی داشته باشیم چی؟
مرسی
وقتی بخوایم کمترین تعدا یال بین یک راس تا بقیه‌ی رئوس رو پیدار کنیم(به طور کلی وقتی وزن همه یکسان باشه این تعدا دیال میشه کوتاهترین مسیر) از BFS استفاده میکنیم
اگه بخوایم وجود حداقل یک دور رو در گراف تشخیص بدیم از DFS استفاده میکنیم
(۲۶ بهمن ۱۳۹۰ ۱۰:۴۵ ق.ظ)homa نوشته شده توسط:ایا____________ همیشه _____میشه کوتاه ترین مسیر را درگراف جهت دار با عمقی پیدا کرد؟(25 بهمن ۱۳۹۰ ۰۴:۵۷ ب.ظ)پشتکار نوشته شده توسط: دوستان کسی میدونه در چه مواقعی از DFS و در چه مواقعی از BFS استفاده می شه؟
و اینکه اگر وزن همه یالهای گراف یکسان باشه کدوم پیمایش بهتره؟ چرا؟
اگر گراف با وزن منفی داشته باشیم چی؟
مرسی
وقتی بخوایم کمترین تعدا یال بین یک راس تا بقیه‌ی رئوس رو پیدار کنیم(به طور کلی وقتی وزن همه یکسان باشه این تعدا دیال میشه کوتاهترین مسیر) از BFS استفاده میکنیم
اگه بخوایم وجود حداقل یک دور رو در گراف تشخیص بدیم از DFS استفاده میکنیم
نقل قول: ایا____________ همیشه _____میشه کوتاه ترین مسیر را درگراف جهت دار با عمقی پیدا کرد؟
کوتاهترین رو با عمقی نمیتونین پیدا کنین!!!
ولی با سطحی میشه[/quote]
(۲۶ بهمن ۱۳۹۰ ۱۰:۴۵ ق.ظ)homa نوشته شده توسط:(25 بهمن ۱۳۹۰ ۰۴:۵۷ ب.ظ)پشتکار نوشته شده توسط: دوستان کسی میدونه در چه مواقعی از DFS و در چه مواقعی از BFS استفاده می شه؟
و اینکه اگر وزن همه یالهای گراف یکسان باشه کدوم پیمایش بهتره؟ چرا؟
اگر گراف با وزن منفی داشته باشیم چی؟
مرسی
وقتی بخوایم کمترین تعدا یال بین یک راس تا بقیه‌ی رئوس رو پیدار کنیم(به طور کلی وقتی وزن همه یکسان باشه این تعدا دیال میشه کوتاهترین مسیر) از BFS استفاده میکنیم
اگه بخوایم وجود حداقل یک دور رو در گراف تشخیص بدیم از DFS استفاده میکنیم
خیلی ممنونم که جواب دادید
میشه بگید این نکات رو از کجا بدست آوردید؟
متشکرم
(۲۶ بهمن ۱۳۹۰ ۱۲:۵۹ ب.ظ)homa نوشته شده توسط:نقل قول: ایا____________ همیشه _____میشه کوتاه ترین مسیر را درگراف جهت دار با عمقی پیدا کرد؟
کوتاهترین رو با عمقی نمیتونین پیدا کنین!!!
ولی با سطحی میشه
[/quote]
مطمئنید با سطحی میشه در گراف جهت دار کوتاه ترین پیدا کرد؟ هزینه همه یالها یکی نیست هاا وزن یالها هم صعودی نیست
(۲۶ بهمن ۱۳۹۰ ۰۱:۳۲ ب.ظ)پشتکار نوشته شده توسط: میشه بگید این نکات رو از کجا بدست آوردید؟من جلد اول CLRS رو دارم که توی اون چیزی راجع به گراف نیست ولی توی کتاب گسسته یوسفی-فصل گراف- یه چیزهای خلاصه ای گفته و کتاب طراحی الگوریتم سپاهان هم توضیحات بیشتری با مثال داده.کتاب ساختمان داده هورویتز هم توضیح داده
(۲۶ بهمن ۱۳۹۰ ۰۳:۲۵ ب.ظ)atharrashno نوشته شده توسط: مطمئنید با سطحی میشه در گراف جهت دار کوتاه ترین پیدا کرد؟ هزینه همه یالها یکی نیست هاا وزن یالها هم صعودی نیستمن هم توی مطالبی که(سریع و نصفه نیمه)خوندم تنها راهی که دیدم همین بود.ولی گفته بود برای پیدا کردن دور تنها از روش عمقی(dfs) میشه رفت
درخت پوشای مینیمم هم از روشهای کروسکال و پریم .
(۲۶ بهمن ۱۳۹۰ ۰۳:۵۱ ب.ظ)fatima1537 نوشته شده توسط:(26 بهمن ۱۳۹۰ ۰۱:۳۲ ب.ظ)پشتکار نوشته شده توسط: میشه بگید این نکات رو از کجا بدست آوردید؟من جلد اول CLRS رو دارم که توی اون چیزی راجع به گراف نیست ولی توی کتاب گسسته یوسفی-فصل گراف- یه چیزهای خلاصه ای گفته و کتاب طراحی الگوریتم سپاهان هم توضیحات بیشتری با مثال داده.کتاب ساختمان داده هورویتز هم توضیح داده
(۲۶ بهمن ۱۳۹۰ ۰۳:۲۵ ب.ظ)atharrashno نوشته شده توسط: مطمئنید با سطحی میشه در گراف جهت دار کوتاه ترین پیدا کرد؟ هزینه همه یالها یکی نیست هاا وزن یالها هم صعودی نیستمن هم توی مطالبی که(سریع و نصفه نیمه)خوندم تنها راهی که دیدم همین بود.ولی گفته بود برای پیدا کردن دور تنها از روش عمقی(dfs) میشه رفت
درخت پوشای مینیمم هم از روشهای کروسکال و پریم .
دوست من تنها راه سطحی نیست بلکه دکستری اصولا واسه این حرفه . مشکل من اینه که کجا گفته تو گراف جهت دار با وزن متفاوت میشه با پیمایش سطحی بهترین مسیر را پیدا کرد؟
(۲۶ بهمن ۱۳۹۰ ۰۷:۴۹ ب.ظ)atharrashno نوشته شده توسط: دوست من تنها راه سطحی نیست بلکه دکستری اصولا واسه این حرفه .نه من منظورم بررسی وجود دور بود نه کوتاهترین مسیر
ساده ترین راه برای بررسی وجود دور در گراف جهت دار الگوریتم dfs هست .