سلام
ممنون بابت پاسخ هایی که به سوالای قبلی م دادید ...
یه سوال دیگه:
آیا جمله زیر صحیح است ؟؟؟ چرا؟
مسیله‌ی یافتن کوتاه ترین مسیرها از یک راس به بقیه‌ی راس‌ها را در یک گراف وزن دار بدون جهت و همبند با مجموعه یالهای E را میتوان در
O(E و نه در O(E+V یافت.
الگوریتم هایی مثل دایکسترا و بلمن فورد و.... برای گراف های جهت دار بودند .... !!! ولی اینجا گراف بدون جهت است
دوست من دکستری هم برای جهت دار بود هم بی جهت و در اینجا علاوه بر دلایلی که قبلا برای اشتباه بودن این جمله ذکر شده باید گفت دکستری میتونه درخت پوشا بسازه (اما نه لزما کمینه) پس درجه اون میتونه o(v+e باشه
(۲۳ بهمن ۱۳۹۰ ۰۶:۴۶ ب.ظ)Anahita.R نوشته شده توسط:اگر از جستجوی درخت کمینه پوشا به روش کروسکال استفاده کنیم میتونه زمان کمتری مصرف بشه
مسیله‌ی یافتن کوتاه ترین مسیرها از یک راس به بقیه‌ی راس‌ها را در یک گراف وزن دار بدون جهت و همبند با مجموعه یالهای E را میتوان در
O(E و نه در O(E+V یافت.
الگوریتم هایی مثل دایکسترا و بلمن فورد و.... برای گراف های جهت دار بودند .... !!! ولی اینجا گراف بدون جهت است
در بدون جهت جستجوی عمقی و سطحی هم میشه ج پیدا کردکه میدونید o(v+e) هست