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

این الگوریتم مرتب‌سازی درخت را که از یک یال شروع شده‌است، افزایش می‌دهد تا جایی که که همه رئوس وارد درخت شوند.

این الگوریتم را به‌طور خلاصه می‌توان چنین شرح داد:

• ورودی: یک گراف همبند وزن دار با مجموعه رئوس 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 بین رئوس و یالها برقرار باشد.

مسئله:یافتن کوچکترین درخت پوشا.

ورودی: عدد صحیح n>=۲و یک گراف بدون جهت و وزن دار و پیوسته شامل n گره. گراف توسط یک آرایه دو بعدی w که سطرها و ستونهایش ار ۱ تا n شاخص دهی شده‌اند نشان داده می‌شود که در ان [w[i][j معرف وزن یال بین گره i ام و گره j ام است.

خروجی:مجموعه‌ای از یال‌ها F در یک درخت پوشای مینیمم برای گراف.

* void prim( int n,
*       const  number w[][],
* set_of_edges & F)
* {
* index i, vnear;
* number min ;
* edge e;
* index nearest[2..n];
* number distance[2..n];
* F = ∅ ;
* for (i = 2; i<=n;i++){
* nearest[i] = 1 ;
* distance[i] = W[1][i];
* }
* repeat (n-1 times){
* min=∞;
* for(i=2; i<=n; i++){
* if(0≤ distance[i] <min){
* min = distance [i];
* vnear = I ;
* }
* e= edge connecting vertices indexed by vnear and nearest[vnear  ];
* add e to F ;
* distance[vnear]= -1
* for (i=2 ; i<= n ;i++)
* if(W[i][vnear] <distance[i]){
* distance[i] = w[i][vnear];
* nearest[i] = vnear;
* }
* }
* }

اگر در لحظه شروع {y={v1 باشد، لذا [nearest[i با ۱ و [distance[i با وزن یال بین v1 و vi مقدار دهی اولیه می‌شود.همان‌طوری‌که گره‌ها به Y اضافه می‌شوند،این دو ارائه برای ارجاع گره جدید در Y به نزدیکترین گره خارج از Y ، به هنگام (update)می‌شوند.برای معین کردن گره‌ای که باید به Y اضافه شوند ،در هر تکرار ،شاخصی که مقدار distance[i]1 ان مینیمم است را محاسبه می‌کنیم. این شاخص را vnear می‌نامیم. با مقداردهی [distance[vnear به۱- ، گره با شاخص vnear به Y اضافه می‌گردد . الگوریتم بالا این روال را پیاده‌سازی می‌کند

if (y!=0)

   p+=e.weight;
     cout<<"("<<e.v1<<","<<e.v2<<") => W :"<<e.weight<<"\t";
      set[e.v1]=0;
 set[e.v2]=0;
 fe++;
 }
 else
 break;
 }
 return p;

 }