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

درخت پوشای کمینه - alifarokhi - 28 آبان ۱۳۹۳ ۰۴:۵۲ ب.ظ

[attachment=17266]زیر درخت پوشای کمینه شکل فوق چی میشه ؟ اگه میشه مراحا اجراشو قدم به قدم توضیح بدید استفاده از روش پریم یا کروسکال تفاوتی نداره

RE: درخت پوشای کمینه - Hamid_0311 - 28 آبان ۱۳۹۳ ۱۰:۰۰ ب.ظ

روش کروسکال که ساده است اول شما میاید و یال ها را براساس وزنشون به صورت صعودی مرتب می کنید یعنی
۷,۸,۱۰,۱۲,۱۳,۱۴
خوب همون طور که می دونیم درخت کمیه تعداد یال هاش یکی از تعداد راس ها کمتره یعنی در این شکل ۴ تا حالت داریم پس باید ۳ تا یال داشته باشیم و با اون ۳ یال به هر ۴ حالت می تونیم دسترسی داشته باشم
خوب میرسیم سر انتخاب یال ها از کمترین یال که ۷ هست شروع می کنیم و یال انتخاب میشه بعد از اون یال با وزن ۸ هستش در انتخاب یال باید دقت کنیم که دور یا حلقه ایجاد نشه خوب یال با وزن ۸ انتخاب میشه چون دوری ایجاد نمی کنه خوب یال بعدی ۱۰ هستش که اون هم چون دوری ایجاد نمی کنه انتخاب میشه و ۳ یال انتخاب شد پس درخت کمینه به دست اومد

دقت کنید اگر مثلا وزن یال ۱۰ و ۱۴ جابه جا بشه دیگه یال ۱۰ انتخاب نمیشه چون ایجاد حلقه می کنه و یال بعدی که کمترین وزن را داره انتخاب میشه یعنی ۱۲
امیدوارم گیچ نشده باشید موفق باشید.Big Grin