الگوریتم پریم با ساختار هیپ چطوریه؟

[MIG]

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

[MIG]

چطور با هیپ الگوریتم پریم رو اجرا کنم؟؟؟

[fatiiiiii]

فقط میدونم مربوط به درس ساختمان داده هاست!

[Mehran NZ]

ببین اگه می گفت کروسکال کار تا حد خیلی زیادی راحت تر بود چون جنگل تشکیل میده و حتما نباید پیوسته باشه کل یالها رو می گرفتی و یه درخت min heap درست می کردی و باقی ماجرا که می شه آب خوردن ولی در پریم باید حالت پیوسته بودن همیشه و در هر مرحله ای حفظ بشه احتمالا راه حل باید به این صورت باشه که به هر نودی از گرافت که رسیدی باید یه min heap برای تمام یالهای همسایش درست کنی و عنصر بالای مین هیپت رو پاپ کنی برای اینکه سایکل تولید نشه هم که برای هر نودت باید فلگ بذاری از یه طرف دیگه فکر کنم باید برنامه با دید بازگشتی نوشته بشه چون ممکنه در یه مرحله به سایکل بخوری و هیچ راهی نداشته باشی و بخوای بری مرحله قبلی شما ببین تو نت یه پیاده سازی درست و حسابی از پریم می تونی پیدا کنی که کمکت کنه چون ساخت هیپ که اصلا کاری نداره با یه ارایه معمولی هم می شه درستش کرد مشکل بیشتر همون پیاده سازی پریم هست در کل مساله جالبی هست اگه وقت و حوصله داشتم انجامش می دادم ولی حیف که ندارم !
در مورد دومی هم تا جایی که می دونم مربوط هست به ساختمان گسسته متاسفانه الان در موردش حضور ذهن ندارم بعدا اگه وقت شد یه نگاه می ندازم و همین پست و ویرایش می کنم خدا رو چه دیدی شاید برنامه اولی رو هم بعدها نوشتم گذاشتم
موفق باشی

[MIG]

ممنون، برنامه رو نوشتم البته با priority queue که در واقع نوعی هیپ به حساب میاد.

[Mehran NZ]

ممنون، برنامه رو نوشتم البته با priority queue که در واقع نوعی هیپ به حساب میاد.

خوب خیلی خوبه ولی چطور می گید که priority queue یک نوع هیپ هست؟!
بله یکی از کاربردهای هیپ ساخت priority queue هست ولی مثلا شما نمی تونی بیای با صف یا پشته درستش کنی و بعد بگی این هیپه !شما 90 درصد کار و انجام دادی بخاطر 10 درصدش کار و خراب نکن(اصولا هدف این سوال این هستش که زمان اجرایی الگوریتم بخاطر استفاده از هیپ پایین بیاد اگه اشتباه نکنم تبدیل می شه به nlogn )
وقت کردی برنامه رو بزار ما هم ببینیم
موفق باشی