(۲۶ بهمن ۱۳۹۰ ۱۰:۴۵ ق.ظ)homa نوشته شده توسط:  

(25 بهمن ۱۳۹۰ ۰۴:۵۷ ب.ظ)پشتکار نوشته شده توسط:  دوستان کسی میدونه در چه مواقعی از DFS و در چه مواقعی از BFS استفاده می شه؟
و اینکه اگر وزن همه یالهای گراف یکسان باشه کدوم پیمایش بهتره؟ چرا؟
اگر گراف با وزن منفی داشته باشیم چی؟
مرسی

وقتی بخوایم کمترین تعدا یال بین یک راس تا بقیه‌ی رئوس رو پیدار کنیم(به طور کلی وقتی وزن همه یکسان باشه این تعدا دیال میشه کوتاهترین مسیر) از BFS استفاده میکنیم

اگه بخوایم وجود حداقل یک دور رو در گراف تشخیص بدیم از DFS استفاده میکنیم

خیلی ممنونم که جواب دادید
میشه بگید این نکات رو از کجا بدست آوردید؟
متشکرم

اگر وزن همه یال‌ها یکسان باشه BFS بهتره . وقتی عمق گراف زیاد باشه BFS بهتره دیگه!!

(۲۶ بهمن ۱۳۹۰ ۱۰:۴۵ ق.ظ)homa نوشته شده توسط:  

(25 بهمن ۱۳۹۰ ۰۴:۵۷ ب.ظ)پشتکار نوشته شده توسط:  دوستان کسی میدونه در چه مواقعی از DFS و در چه مواقعی از BFS استفاده می شه؟
و اینکه اگر وزن همه یالهای گراف یکسان باشه کدوم پیمایش بهتره؟ چرا؟
اگر گراف با وزن منفی داشته باشیم چی؟
مرسی

وقتی بخوایم کمترین تعدا یال بین یک راس تا بقیه‌ی رئوس رو پیدار کنیم(به طور کلی وقتی وزن همه یکسان باشه این تعدا دیال میشه کوتاهترین مسیر) از BFS استفاده میکنیم

اگه بخوایم وجود حداقل یک دور رو در گراف تشخیص بدیم از DFS استفاده میکنیم

ایا____________ همیشه _____میشه کوتاه ترین مسیر را درگراف جهت دار با عمقی پیدا کرد؟

نقل قول: ایا____________ همیشه _____میشه کوتاه ترین مسیر را درگراف جهت دار با عمقی پیدا کرد؟

کوتاهترین رو با عمقی نمیتونین پیدا کنین!!!

ولی با سطحی میشه[/quote]

(۲۶ بهمن ۱۳۹۰ ۰۱:۳۲ ب.ظ)پشتکار نوشته شده توسط:  میشه بگید این نکات رو از کجا بدست آوردید؟

من جلد اول CLRS رو دارم که توی اون چیزی راجع به گراف نیست ولی توی کتاب گسسته یوسفی-فصل گراف- یه چیزهای خلاصه ای گفته و کتاب طراحی الگوریتم سپاهان هم توضیحات بیشتری با مثال داده.کتاب ساختمان داده هورویتز هم توضیح داده

---

(۲۶ بهمن ۱۳۹۰ ۰۳:۲۵ ب.ظ)atharrashno نوشته شده توسط:  مطمئنید با سطحی میشه در گراف جهت دار کوتاه ترین پیدا کرد؟ هزینه همه یالها یکی نیست هاا وزن یالها هم صعودی نیست

من هم توی مطالبی که(سریع و نصفه نیمه)خوندم تنها راهی که دیدم همین بود.ولی گفته بود برای پیدا کردن دور تنها از روش عمقی(dfs) میشه رفت
درخت پوشای مینیمم هم از روشهای کروسکال و پریم .

(۲۶ بهمن ۱۳۹۰ ۰۳:۵۱ ب.ظ)fatima1537 نوشته شده توسط:  

(26 بهمن ۱۳۹۰ ۰۱:۳۲ ب.ظ)پشتکار نوشته شده توسط:  میشه بگید این نکات رو از کجا بدست آوردید؟

من جلد اول CLRS رو دارم که توی اون چیزی راجع به گراف نیست ولی توی کتاب گسسته یوسفی-فصل گراف- یه چیزهای خلاصه ای گفته و کتاب طراحی الگوریتم سپاهان هم توضیحات بیشتری با مثال داده.کتاب ساختمان داده هورویتز هم توضیح داده

---

(۲۶ بهمن ۱۳۹۰ ۰۳:۲۵ ب.ظ)atharrashno نوشته شده توسط:  مطمئنید با سطحی میشه در گراف جهت دار کوتاه ترین پیدا کرد؟ هزینه همه یالها یکی نیست هاا وزن یالها هم صعودی نیست

من هم توی مطالبی که(سریع و نصفه نیمه)خوندم تنها راهی که دیدم همین بود.ولی گفته بود برای پیدا کردن دور تنها از روش عمقی(dfs) میشه رفت
درخت پوشای مینیمم هم از روشهای کروسکال و پریم .

دوست من تنها راه سطحی نیست بلکه دکستری اصولا واسه این حرفه . مشکل من اینه که کجا گفته تو گراف جهت دار با وزن متفاوت میشه با پیمایش سطحی بهترین مسیر را پیدا کرد؟

(۲۶ بهمن ۱۳۹۰ ۰۷:۴۹ ب.ظ)atharrashno نوشته شده توسط:  دوست من تنها راه سطحی نیست بلکه دکستری اصولا واسه این حرفه .

نه من منظورم بررسی وجود دور بود نه کوتاهترین مسیر

ساده ترین راه برای بررسی وجود دور در گراف جهت دار الگوریتم dfs هست .