تالار گفتمان مانشت
درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - نسخه‌ی قابل چاپ

درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - zahra2012 - 22 بهمن ۱۳۹۲ ۱۱:۵۰ ق.ظ

میخواهیم در یک گراف درخت پوشاب کمینه را به نحوی بیابیم که حتما شامل دو یال e1,e2 باشه بهترین الگوریت برای این کار چه هزینه ای دارد؟
جواب elogv هست میشه بگین چرا؟

RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - masoud67 - 22 بهمن ۱۳۹۲ ۱۱:۵۴ ق.ظ

(۲۲ بهمن ۱۳۹۲ ۱۱:۵۰ ق.ظ)zahra2012 نوشته شده توسط:  میخواهیم در یک گراف درخت پوشاب کمینه را به نحوی بیابیم که حتما شامل دو یال e1,e2 باشه بهترین الگوریت برای این کار چه هزینه ای دارد؟
جواب elogv هست میشه بگین چرا؟
اول اون دو یا را انتخاب میکنید و بعد مثل روال کراسکال یا پریم شروع میکنید جستجو و اضافه کردن یالها.
زمانش هم چون از هیپ دو جمله ای استفاده کرده میشه elogv

RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - zahra2012 - 22 بهمن ۱۳۹۲ ۱۲:۳۷ ب.ظ

(۲۲ بهمن ۱۳۹۲ ۱۱:۵۴ ق.ظ)masoud67 نوشته شده توسط:  
(22 بهمن ۱۳۹۲ ۱۱:۵۰ ق.ظ)zahra2012 نوشته شده توسط:  میخواهیم در یک گراف درخت پوشاب کمینه را به نحوی بیابیم که حتما شامل دو یال e1,e2 باشه بهترین الگوریت برای این کار چه هزینه ای دارد؟
جواب elogv هست میشه بگین چرا؟
اول اون دو یا را انتخاب میکنید و بعد مثل روال کراسکال یا پریم شروع میکنید جستجو و اضافه کردن یالها.
زمانش هم چون از هیپ دو جمله ای استفاده کرده میشه elogv
مرسی اینجا چون فقط زمان هیپ هست این رو انتخاب کردیم اگر پیاده سازی ماتریس و هرم فیبونانچی بود تو صورت چیزی نگفته بود در مورد شلوغی و اینا اولویت با کدوم بود ؟
بازم ممنون که تو این روزا جواب سوالا رو میدین

RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - masoud67 - 22 بهمن ۱۳۹۲ ۱۲:۴۲ ب.ظ

(۲۲ بهمن ۱۳۹۲ ۱۲:۳۷ ب.ظ)zahra2012 نوشته شده توسط:  
(22 بهمن ۱۳۹۲ ۱۱:۵۴ ق.ظ)masoud67 نوشته شده توسط:  
(22 بهمن ۱۳۹۲ ۱۱:۵۰ ق.ظ)zahra2012 نوشته شده توسط:  میخواهیم در یک گراف درخت پوشاب کمینه را به نحوی بیابیم که حتما شامل دو یال e1,e2 باشه بهترین الگوریت برای این کار چه هزینه ای دارد؟
جواب elogv هست میشه بگین چرا؟
اول اون دو یا را انتخاب میکنید و بعد مثل روال کراسکال یا پریم شروع میکنید جستجو و اضافه کردن یالها.
زمانش هم چون از هیپ دو جمله ای استفاده کرده میشه elogv
مرسی اینجا چون فقط زمان هیپ هست این رو انتخاب کردیم اگر پیاده سازی ماتریس و هرم فیبونانچی بود تو صورت چیزی نگفته بود در مورد شلوغی و اینا اولویت با کدوم بود ؟
بازم ممنون که تو این روزا جواب سوالا رو میدین
اولویت با کمترین مقداره
ماتریس میشه N به توان ۲
هیپ دو جمله ای همیشه elogv
و هیپ فیبوناچی میشه e+nlogn
توی حالت همه چی نامعلوم اصلا معلوم نیست کدوم کمتره

RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - zahra2012 - 22 بهمن ۱۳۹۲ ۰۱:۰۰ ب.ظ

(۲۲ بهمن ۱۳۹۲ ۱۲:۴۲ ب.ظ)masoud67 نوشته شده توسط:  
(22 بهمن ۱۳۹۲ ۱۲:۳۷ ب.ظ)zahra2012 نوشته شده توسط:  
(22 بهمن ۱۳۹۲ ۱۱:۵۴ ق.ظ)masoud67 نوشته شده توسط:  
(22 بهمن ۱۳۹۲ ۱۱:۵۰ ق.ظ)zahra2012 نوشته شده توسط:  میخواهیم در یک گراف درخت پوشاب کمینه را به نحوی بیابیم که حتما شامل دو یال e1,e2 باشه بهترین الگوریت برای این کار چه هزینه ای دارد؟
جواب elogv هست میشه بگین چرا؟
اول اون دو یا را انتخاب میکنید و بعد مثل روال کراسکال یا پریم شروع میکنید جستجو و اضافه کردن یالها.
زمانش هم چون از هیپ دو جمله ای استفاده کرده میشه elogv
مرسی اینجا چون فقط زمان هیپ هست این رو انتخاب کردیم اگر پیاده سازی ماتریس و هرم فیبونانچی بود تو صورت چیزی نگفته بود در مورد شلوغی و اینا اولویت با کدوم بود ؟
بازم ممنون که تو این روزا جواب سوالا رو میدین
اولویت با کمترین مقداره
ماتریس میشه N به توان ۲
هیپ دو جمله ای همیشه elogv
و هیپ فیبوناچی میشه e+nlogn
توی حالت همه چی نامعلوم اصلا معلوم نیست کدوم کمتره

ممنون Smile

RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - mohammad.ardeshiri - 22 بهمن ۱۳۹۲ ۰۲:۱۰ ب.ظ

bainery heap ===========>((V+E)logv));l
میشه

RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - zahra2012 - 22 بهمن ۱۳۹۲ ۰۲:۲۳ ب.ظ

(۲۲ بهمن ۱۳۹۲ ۰۲:۱۰ ب.ظ)mohammad.ardeshiri نوشته شده توسط:  bainery heap ===========>((V+E)logv));l
میشه

بله فرمول دقیقش این هست ولی چون اصولن یالها بیشتر از گره ها هستن اون رو به کار می برن

RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - mohammad.ardeshiri - 22 بهمن ۱۳۹۲ ۰۲:۲۸ ب.ظ

(۲۲ بهمن ۱۳۹۲ ۰۲:۲۳ ب.ظ)zahra2012 نوشته شده توسط:  
(22 بهمن ۱۳۹۲ ۰۲:۱۰ ب.ظ)mohammad.ardeshiri نوشته شده توسط:  bainery heap ===========>((V+E)logv));l
میشه

بله فرمول دقیقش این هست ولی چون اصولن یالها بیشتر از گره ها هستن اون رو به کار می برن

توسوالای که حرفی زده نشده مثل بالا حتما باید این فرمول به کار بره

RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - zahra2012 - 22 بهمن ۱۳۹۲ ۰۲:۴۹ ب.ظ

(۲۲ بهمن ۱۳۹۲ ۰۲:۲۸ ب.ظ)mohammad.ardeshiri نوشته شده توسط:  
(22 بهمن ۱۳۹۲ ۰۲:۲۳ ب.ظ)zahra2012 نوشته شده توسط:  
(22 بهمن ۱۳۹۲ ۰۲:۱۰ ب.ظ)mohammad.ardeshiri نوشته شده توسط:  bainery heap ===========>((V+E)logv));l
میشه

بله فرمول دقیقش این هست ولی چون اصولن یالها بیشتر از گره ها هستن اون رو به کار می برن

توسوالای که حرفی زده نشده مثل بالا حتما باید این فرمول به کار بره

این سوال بود یا جواب؟Exclamation

RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - mohammad.ardeshiri - 22 بهمن ۱۳۹۲ ۰۳:۵۷ ب.ظ

(۲۲ بهمن ۱۳۹۲ ۰۲:۴۹ ب.ظ)zahra2012 نوشته شده توسط:  
(22 بهمن ۱۳۹۲ ۰۲:۲۸ ب.ظ)mohammad.ardeshiri نوشته شده توسط:  
(22 بهمن ۱۳۹۲ ۰۲:۲۳ ب.ظ)zahra2012 نوشته شده توسط:  
(22 بهمن ۱۳۹۲ ۰۲:۱۰ ب.ظ)mohammad.ardeshiri نوشته شده توسط:  bainery heap ===========>((V+E)logv));l
میشه

بله فرمول دقیقش این هست ولی چون اصولن یالها بیشتر از گره ها هستن اون رو به کار می برن

توسوالای که حرفی زده نشده مثل بالا حتما باید این فرمول به کار بره

این سوال بود یا جواب؟Exclamation
نظره شخصیمه ولی با کراسکال نمیشه اینکارو کرد با پریم میشه اینکارو کرد اونم بهترین مرتبش اینه

RE: درخت پوشای کمینه به طوری که حتما شامل دو یال باشد - zahra2012 - 23 بهمن ۱۳۹۲ ۱۱:۱۸ ق.ظ

(۲۲ بهمن ۱۳۹۲ ۰۳:۵۷ ب.ظ)mohammad.ardeshiri نوشته شده توسط:  
(22 بهمن ۱۳۹۲ ۰۲:۴۹ ب.ظ)zahra2012 نوشته شده توسط:  
(22 بهمن ۱۳۹۲ ۰۲:۲۸ ب.ظ)mohammad.ardeshiri نوشته شده توسط:  
(22 بهمن ۱۳۹۲ ۰۲:۲۳ ب.ظ)zahra2012 نوشته شده توسط:  
(22 بهمن ۱۳۹۲ ۰۲:۱۰ ب.ظ)mohammad.ardeshiri نوشته شده توسط:  bainery heap ===========>((V+E)logv));l
میشه

بله فرمول دقیقش این هست ولی چون اصولن یالها بیشتر از گره ها هستن اون رو به کار می برن

توسوالای که حرفی زده نشده مثل بالا حتما باید این فرمول به کار بره

این سوال بود یا جواب؟Exclamation
نظره شخصیمه ولی با کراسکال نمیشه اینکارو کرد با پریم میشه اینکارو کرد اونم بهترین مرتبش اینه

ممنون