مرکز انجمنهای تخصصی

سلام.

در مباحث طراحی الگوریتم یه الگوریتمی وجود داره به نام درخت پوشای مینیمال که دوستانی که احتمالا درس و موضوعات مربوط به اون رو مطالعه کردن با این مبحث هم به خوبی آشنایی دارن .

بعد از بررسی این الگوریتم قرار بر این شد که شکل الگوریتم رو تغییر بدیم طوری که درخت ماکسیمال تولید کنه ولی من هرچی رو الگوریتم فکر کردم نتونستم یه راه براش پیدا کنم .
ممکنه اگر کسی در این رابطه اطلاعاتی داره در اختیارم قرار بده ؟حلش خیلی برام مهمه .

ممنونم

برای یافتن درخت پوشای مینیمال سه الگوریتم مشهور وجود داره: الگوریتم دیکسترا که یک روش greedy هست، الگوریتم کراسکال و الگوریتم پریم. چون شما مشخص نکرده بودید منظورتون تغییر کدام الگوریتم هست، من خودم کراسکال رو انتخاب کردم. امیدوارم منظورتون همون باشه چون برعکس کردن الگوریتم های greedy که اصولا کار خیلی سختی نیست...
برای این کار راهی که به نظر من رسید اینه که:
ابتدا مجموعه رئوس رو به عنوان مجموعه درخت ها در نظر میگیریم. سپس مجموعه ی یالها رو به صورت نزولی مرتب میکنیم. حال در یک for loop سعی میکنیم به ترتیب یالها با بزرگترین وزن رو انتخاب کنیم به این صورت که ایجاد دور نکند. یعنی چک میکنیم اگر دو راسی که این یال به آنها تعلق دارد، اگر در حال حاضر در یک درخت هستند، این راس را نمیتوان در نظر گرفت. و اگر در یک درخت نیستند آنها را با این یال(که بیشترین وزن بین یالهای ممکن بین این دو گراف را دارد، چون یالها را بر اساس وزن به صورت نزولی مرتب کرده ایم) به هم وصل می کنیم.

سلام

محبت میکنید روی الگوریتم پریم توضیح بدید و منظورم از اعمال تغییرات روی برنامه یا حداقل روی شبه کد هست .اگر شبه کد برنامه رو در اختیار ندارید بفرمایید تا بنده بذارم و روی اون بحث کنیم .

خیلی ممنون.

الگوریتم پریم به صورت زیر در میاید:

 Please Login or Register to see this code   در آنG یک Connected Graph است، و r یک گره فرضی که به عنوان ریشه به برنامه پاس میشه!
[U][U]
[/U][/U]

بسیار بسیار ممنونم . اما ممکنه بفرمایید تغییرات رو روی این الگوریتم باید چطور اعمال کنیم .

Please Login or Register to see this code