سلام.
این اولین پستم تو فروم شما. امیدوارم تو زمینه گراف راهنمایی کنید. من چه جوری میتونم گراف که ضمیمه کردم بر طبق کراسکال حلش کنم؟[attachment=5443]
سلام. این شکل، شکل کتاب گریمالدیه. برای الگوریتم کروسکال باید اول به یالهات اسم بدی و اونا رو به ترتیب اندازه مرتب کنی. ۷ تا راس داری پس باید ۶ تا یال رو به ترتیب انتخاب کنی به شرطی که با انتخاب هر یال، دور ایجاد نشه.
یال اول و دوم رو انتخاب کن. اگه با انتخاب یال سوم دور ایجاد میشه اونو انتخاب نکن. برای یالهای بعدی هم مثل یال سوم عمل میکنیم. هروقت ۶تا یال انتخاب شد درخت بدست میاد.
شرط برای n-1 یال الزامی نیست. بیشتر از این تعداد انتخاب نمیشه. ولی شرط، بدست آوردن جوابو سریعتر میکنه.
ممنون از راهنماییتون..
تو اینجا a,b,d نمیشه انتخاب کرد اما چون دور ایجا میشه منظورتون از دور همینه؟ که گراف نبنده؟
فکر کنم متوجه نشدید. a و b و d همشون راسن. توی کروسکال با یال کار میکنیم. مثلاً ed و eg و dg باهم انتخاب نمیشن. کروسکال برای بدست آوردن درخت حداقله. درخت هم باید همبند باشه و نباید دور داشته باشه.
میشه درخت بکشید و توضیح بدید
(۱۳ تیر ۱۳۹۱ ۰۱:۴۸ ب.ظ)moh3en نوشته شده توسط: میشه درخت بکشید و توضیح بدید
۵+۴+۳+۲+۲+۱=۱۷
میشه درخت بکشید و توضیح بدید
۵+۴+۳+۲+۲+۱=۱۷
برای کشیدن درخت مینیمم باید کوتاه ترین یال ها رو انتخاب کنیم
همون طور که در شکلم نوشتم اون ترتیبیه که یال ها رو انتخاب میکنیم
و در درخت پوشای مینیمم نباید دور ایجاد بشه