تالار گفتمان مانشت

سلام

ممنون بابت پاسخ هایی که به سوالای قبلی م دادید ...

یه سوال دیگه:

آیا جمله زیر صحیح است ؟؟؟ چرا؟

مسیله‌ی یافتن کوتاه ترین مسیرها از یک راس به بقیه‌ی راس‌ها را در یک گراف وزن دار بدون جهت و همبند با مجموعه یالهای E را میتوان در
O(E و نه در O(E+V یافت.


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

دوست من دکستری هم برای جهت دار بود هم بی جهت و در اینجا علاوه بر دلایلی که قبلا برای اشتباه بودن این جمله ذکر شده باید گفت دکستری میتونه درخت پوشا بسازه (اما نه لزما کمینه) پس درجه اون میتونه o(v+e باشه

(23 بهمن 1390 06:46 ب.ظ)Anahita.R نوشته شده توسط: [ -> ]
مسیله‌ی یافتن کوتاه ترین مسیرها از یک راس به بقیه‌ی راس‌ها را در یک گراف وزن دار بدون جهت و همبند با مجموعه یالهای E را میتوان در
O(E و نه در O(E+V یافت.


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

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

در بدون جهت جستجوی عمقی و سطحی هم میشه ج پیدا کردکه میدونید o(v+e) هست