الگوریتم Prim
Prim's AlgorithmPrim یک Minimum Spanning Tree را از یک Node شروع می‌کند و هر بار ارزان‌ترین edgeای را اضافه می‌کند که tree فعلی را به یک Node جدید وصل کند.
اول این مفهوم را در ذهن نگه دار
Prim یک Minimum Spanning Tree را از یک Node شروع می‌کند و هر بار ارزان‌ترین edgeای را اضافه می‌کند که tree فعلی را به یک Node جدید وصل کند.
چطور کار می‌کند؟ ساده و مرحله‌ای
edgeهای مرزی را با Min Priority Queue مدیریت کن.
برخلاف Kruskal، Prim در تمام مدت یک tree متصل را گسترش می‌دهد.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
مشخص کن گراف directed/undirected و weighted/unweighted است.
representation گراف را انتخاب کن.
state الگوریتم و حالت disconnected/cycle را صریح مدیریت کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای الگوریتم Prim هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
O(E log V)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- فقط وقتی assumptionهای الگوریتم با مسئله گراف هماهنگ است از آن استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- فراموش کردن componentهای disconnected.
- قاطی کردن shortest path وزن‌دار و بدون وزن.
- مدیریت نکردن revisit/cycle.
مدل یک پاسخ حرفه‌ای
Prim و Kruskal را مفهومی مقایسه کن و نگو یکی همیشه سریع‌تر است؛ density و representation گراف مهم‌اند.
الگوریتم Prim چه مسئله‌ای را حل می‌کند؟
Prim یک Minimum Spanning Tree را از یک Node شروع می‌کند و هر بار ارزان‌ترین edgeای را اضافه می‌کند که tree فعلی را به یک Node جدید وصل کند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(E log V) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
فراموش کردن componentهای disconnected.