الگوریتم پریم

الگوریتم پریم، پیدا کردن درخت فراگیر مینیمال
الگوریتم پریم ، الگوریتمی در نظریه گراف‌ها است که زیردرخت پوشای کمینه را برای یک گراف همبند وزن دار پیدا می‌کند یعنی زیرمجموعه‌ای از یال‌ها را در آن گراف می‌یابد که درختی را تشکیل می‌دهند که همه رئوس را شامل می‌شود در حالیکه مجموع وزن همه آن یال‌ها کمینه شده‌است. این الگوریتم در سال ۱۹۳۰ توسط ریاضیدانی به نام جارنیک داده شد و سپس در سال ۱۹۵۷ پریم، دانشمند علوم کامپیوتر آن را مستقل از جارنیک کشف کرد و در سال ۱۹۵۹ دایکسترا دوباره به آن دست یافت. ازاین رو این الگوریتم گاهی با نام الگوریتم DJP نیز شناخته می‌شود که برگرفته از اسامی دایکسترا، جارنیک و پریم است.
شرح الگوریتم
این الگوریتم مرتب‌سازی درخت را که از یک یال شروع شده‌است، افزایش می‌دهد تا جایی که که همه رئوس وارد درخت شوند.
این الگوریتم را به‌طور خلاصه می‌توان چنین شرح داد:
ورودی: یک گراف همبند وزن دار با مجموعه رئوس V و یالهای E
مقدار دهی اولیه: {V new = {x که V new مجموعه رئوس درخت پوشای کمینه در حالت آغازین را نشان می‌دهد و x یک راس دلخواه است (نقطه شروع) و = E new که E new بیانگر مجموعه یالهای این درخت است.
حلقه زیر را تا وقتی که V new = V تکرار کن:
یال (u,v) را با وزن کمینه انتخاب کن به‌طوری‌که u در V new قرار داشته باشد ولی v عضوی از این مجموعه نباشد (اگر چند یال باوزن یکسان وجود دارند یکی را به دلخواه انتخاب کن)
راس v را به V new و یال (u , v) رابه E new اضافه کن.
خروجی :V new و E new درخت پوشا. کمینه را توصیف می‌کنند.
نکته: الگوریتم پریم را به این صورت نیزمی توان بیان کرد:ابتدا گره‌ای به دلخواه انتخاب شود و سپس از بین یالهای متصل به آن یالی با کمترین وزن انتخاب می‌شود به گونه‌ای که حلقه ایجاد نشود. در هر مرحله یالی انتخاب می‌شود که حتما یکی از دو سرآن جزو مسیر جواب بوده و وزن حداقل داشته باشد. پس در الگوریتم پریم دو محدودیت در هر مرحله داریم یکی آن که جنگل ایجاد نشود و دوم آنکه حلقه شکل نگیرد.
از آنجا که در الگوریتم پریم در هر مرحله فاصله هر گره با گره‌های قبلی مقایسه می‌شود پس بدیهی است که از مرتبه (n2) می‌باشد که n تعداد رئوس گراف است.
هزینه زمانی
یک پیاده‌سازی ساده، استفاده از نمایش گراف به صورت ماتریس مجاورت است که درآن به دنبال آرایه‌ای از وزنها باشیم و یال‌های با وزن کمینه را به مجموعه خود اضافه کنیم. این روش (O(V ۲ زمان می‌برد. الگوریتم پریم بااستفاده از داده ساختار هیپ دودویی ساده و نمایش فهرست مجاورت می‌تواند در زمان (O(E log V اجرا شود که در آن E تعداد یالها و V تعداد رئوس است. استفاده از مدل پیچیده‌تری به نام هیپ فیبوناچی باعث می‌شود این زمان تا حد (O(E + V log V کاهش یابد. سرعت این روش به خصوص زمانی آشکار می‌شود که در گراف رابطه (E = (V بین رئوس و یالها برقرار باشد.
مثال
شکل
شرح
200px
این شکل گراف وزن دار اصلی را نشان می‌دهد. اعداد کنار هر یال بیانگر وزن آن یال هستند.
200px
راس D به‌طور دلخواه به عنوان نقطه شروع انتخاب شده‌است. رئوس A ، B ، E ، F همگی با یالی به D متصل هستند. A نزدیک‌ترین راس به D است بنابراین همراه با یال AD برای درخت انتخاب می‌گردد.
200px
راس بعدی که انتخاب می‌شود باید نزدیک‌ترین راس به A یا D باشد. فاصله B از D برابر ۹ و فاصله آن از A برابر ۷ است. فواصل E و F نیز به ترتیب ۱۵ و ۶ می‌باشد. راس F کمترین فاصله را دارد بنابراین این راس و کمان DF را انتخاب می‌کنیم.
200px
الگوریتم مشابه بالا ادامه می‌یابد و راس B که فاصله‌اش از A برابر ۷ است انتخاب می‌شود.
200px
در این حالت انتخاب ما بین C ، E ، G می‌تواند صورت گیرد. فاصله C از B برابر ۸، فاصله E ازآن برابر ۷ و فاصله G از F نیز ۱۱ است. مشاهده می‌شود که E نزدیک‌ترین راس است پس آن را همراه با کمان BE انتخاب می‌کنیم.
200px
در اینجا تنها رئوس C و G باقی‌مانده‌اند. فاصله C از E برابر ۵ و فاصله G از آن ۹ است پس C انتخاب می‌شود و کمان CE نیز هم‌زمان با آن وارد درخت می‌گردد.
200px
تنها راس باقی‌مانده G است که چون فاصله‌اش از E کمتر از فاصله‌اش تا F می‌باشد، یال EG را انتخاب می‌کنیم.
200px
در پایان همه رئوس انتخاب شده‌اند و درخت پوشای کمینه با رنگ سبز نشان داده شده‌است که وزنی برابر ۳۹ دارد.
شبه کد الگوریتم پریم
مسئله:یافتن کوچکترین درخت پوشا.
ورودی: عدد صحیح n>=۲و یک گراف بدون جهت و وزن دار و پیوسته شامل n گره. گراف توسط یک آرایه دو بعدی w که سطرها و ستونهایش ار ۱ تا n شاخص دهی شده‌اند نشان داده می‌شود که در ان wij معرف وزن لبه بین گره i ام و گره j ام است .
خروجی:مجموعه‌ای از لبه‌ها F در یک درخت پوشای مینیمم برای گراف.
void prim( int n,
const number w,
set_of_edges - F)
index i, vnear;
number min ;
edge e;
index nearest ;
number distance ;
F = ∅ ;
for (i = 2; i<=n;i++){
nearesti = 1 ;
distancei = W1i;
repeat (n-1 times){
min=∞;
for(i=2; i<=n; i++){
if(0≤ distancei <min){
min = distance i;
vnear = I ;
e= edge connecting vertices indexed by vnear and nearestvnear ;
add e to F ;
distancevnear= -1
for (i=2 ; i<= n ;i++)
if(Wivnear <distancei){
distancei = wivnear;
nearesti = vnear;
اگر در لحظه شروع {y={v1 باشد، لذا nearesti با ۱ و distancei با وزن لبه بین v1 و vi مقدار دهی اولیه می‌شود.همان‌طوری‌که گره‌ها به Y اضافه می‌شوند،این دو ارائه برای ارجاع گره جدید در Y به نزدیکترین گره خارج از Y ، به هنگام (update)می‌شوند.برای معین کردن گره‌ای که باید به Y اضافه شوند ،در هر تکرار ،شاخصی که مقدار distancei1 ان مینیمم است را محاسبه می‌کنیم. این شاخص را vnear می‌نامیم. با
مقداردهی distancevnear به۱- ، گره با شاخص vnear به Y اضافه می‌گردد . الگوریتم بالا این روال را پیاده‌سازی می‌کند
if (y!=0)
p+=e.weight;
cout W :"<<e.weight<<"\t";
set =0;
set =0;
fe++;
else
break;
return p;