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

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

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

1. راس‌های گراف را به دو مجوعه $V'$ (شامل همه راس‌های گراف به جز راس دلخواه v) و $V$ (شامل v) افراز کن.
2. تا زمانی که $V$ شامل تمام راس‌ها نشده کار‌های زیر را انجام بده
   1. بین تمام یال‌هایی که بین مجوعه $V$ و $V'$ کم‌وزن‌ترین را انتخاب کن(مثلا یال (u,v) که u در $V$).
   2. راس v را از $V'$ حذف و به $V$ اضافه کن.
   3. یال (u,v) را به عنوان یالی از درخت پوشای کمینه انتخاب کن.
3. پایان

ادعا: اگر گراف را به دو مجموعه $V$ و $V'$ از راس‌ها افراز کنیم، کم‌وزن‌ترین یال بین یال‌هایی که یک طرفشان در مجموعه $V$ و طرف دیگرشان در مجموعه $V'$ است باید جزء درخت پوشای کمینه باشد. (اگر چند یال با کم‌ترین وزن وجود داشت، باید دقیقا یکی از آن‌ها جزء درخت پوشای کمینه باشد)

اثبات: اگر یالی بین این دو مجموعه انتخاب نشود، گراف همبند نمی‌شود، اگر ۲ یال یا بیشتر انتخاب شود با فرض همبندی در هر دو مجموعه دور ایجاد خواهد شد. و اگر یالی که کمترین وزن را ندارد انتخاب شود، می‌توان با عوض کردن آن با کم‌وزن ترین ویژگی های درخت را حفظ کرد و مجموع وزن ها را کاهش داد. پس کم‌وزن‌ترین انتخاب می‌شود.

این ادعا صحت الگوریتم را در هر مرحله ثابت می‌کند.

تصویر زیر نمایشی از اجرای الگوریتم پریم روی یک مثال است. یال‌های سیاه، گزینه‌هایی انتخابی در هر مرحله‌اند. یال‌های قرمز و راس‌های سیاه انتخاب شده‌اند. یال‌ها و راس‌های خاکستری انتخاب نشده‌اند.

یک روش خوب برای بهینه کردن الگوریتم نگه داشتن کم‌ترین فاصله‌ی هر راس تا راس‌های انتخابیست. وقتی یک راس به مجموعه‌ی ما اضافه شد. فاصله‌ی بقیه راس‌ها را به روز می‌کنیم. در این صورت هر بار برای پیدا کردن راس نزدیک‌تر و به روز رسانی $O(n)$ عملیات انجام می‌دهیم و چون $n$ بار این کار انجام می‌دهیم، پیچیدگی کل الگوریتم $O(n^2)$ می‌شود. اگر فاصله‌هر راس تا نزدیک‌‌ترین راس از بین راس‌هایی که در مجموعه قرار گرفته‌اند را در داه‌ساختاری مناسب ذخیره کنیم می‌توانیم پیچیدگی الگوریتم را بهتر کنیم. اگر این داده‌ساختار هرم کمینه باشد، چون حذف و اضافه از $O(log n)$ است و به ازای یال حداکثر یک بار عملیات اضافه کردن رخ می‌دهد و چون قطعا تعداد عملیات حذف کم‌تر از تعداد عملیات اضافه کردن است پیچیدگی الگوریتم به $O(mlogn+n)$ تغییر می‌کند که برای حالاتی که تعداد یال‌ها از $\theta(\frac{n^2}{logn})$ کم‌تر باشد پیچیدگی کل کاهش پیدا می‌کند. حال اگر از هرم فیبوناچی استفاده کنیم پیچیدگی به $O(m+n)$ کاهش پیدا می‌کند.

Prim.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF=2*1000*1000*1000+5; // ثابتی بسیار بزرگ که از هر ورودی بزرگ‌تر باشد
const int N=1000; // حداکثر تعداد راس‌ها
int n,m; //به ترتیب تعداد راسها، تعداد یال‌ها
int min_e[N]; // کم‌ترین فاصله‌ی هر راس تا راس‌های انتخاب شده
int sel_e[N]; // نزدیک‌ترین راس از بین راس‌های انتخاب شده
bool used[N]; // جزء مجموعه شده یا نه
vector <pair<int,int> > ans; // پشته‌ای که جواب را نگه می‌دارد
vector <pair<int,int> > V[N]; // وزن و شماره راس‌هایی که به آن یال دارد
bool find_mst(){
	fill_n(min_e,n,INF); // مقدار دهی اولیه
	fill_n(sel_e,n,-1);  // مقدار دهی اولیه
	fill_n(used,n,false);  // مقدار دهی اولیه
	min_e[0]=0;	 // صفر قرار می‌دهیم تا ابتدا راس صفر(یک) انتخاب شود
	for (int i=0; i<n; i++) {
		int v = -1;
		for (int j=0; j<n; j++)
			if (!used[j] && (v == -1 || min_e[j] < min_e[v]))
				v = j;
 
		if (min_e[v] == INF) 
			return false; // هیچ یالی از راس‌هایی انتخابی به بیرون وجود ندارد
 
		used[v] = true;
		if (sel_e[v] != -1)
			ans.push_back(make_pair(sel_e[v],v)); // به مجموعه v اضافه کردن راس
 
		for (int j=0; j<(int)V[v].size(); j++) // به روز کردن مقادیر آرایه‌ها
			if (V[v][j].second < min_e[V[v][j].first]) {
				min_e[V[v][j].first] =V[v][j].second;
				sel_e[V[v][j].first] = v;
			}
	}
	return true;
}
 
int main() {	
	cin >> n>>m;
	for(int i=0; i<m; i++){ // حلقه گرفتن یال‌ها
		int a,b,w;
		cin >>a>>b>>w; // به ترتیب ۲ راس و سپس وزن یال
		V[a-1].push_back(make_pair(b-1,w)); // است n-1 یکی کم می‌کنیم چون بازه‌ی معتبر ما صفر تا
		V[b-1].push_back(make_pair(a-1,w)); // است n-1 یکی کم می‌کنیم چون بازه‌ی معتبر ما صفر تا
	}
	if(find_mst()==false)
		cout << "No MST!\n";
}

در انتها پشته‌ی ans شامل یال‌های درخت پوشای کمینه است.

این‌بار نزدیک‌ترین راس‌از بین راس‌های انتخاب شده را در یک داده‌ساختار آماده ++C به اسم set می‌ریزیم که عملیات حذف و اضافه را در $O(log n)$ انجام می‌دهد و پیچیدگی کل را به $O(mlogn+n)$ تغییر می‌دهد. این پیاده‌سازی برای زمانی که تعداد یال‌ها خیلی زیاد نباشد سریع‌تر از پیاده‌سازی اولیه عمل می‌کند.

prim-min_heap.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF=2*1000*1000*1000+5; // ثابتی بسیار بزرگ که از هر ورودی بزرگ‌تر باشد
const int N=1000; // حداکثر تعداد راس‌ها
int n,m; //به ترتیب تعداد راس‌ها، تعداد یال‌ها
int min_e[N]; // کم‌ترین فاصله‌ی هر راس تا راس‌های انتخاب شده
int sel_e[N]; // نزدیک‌ترین راس از بین راس‌های انتخاب شده
vector <pair<int,int> > ans; // پشته‌ای که جواب را نگه می‌دارد
vector <pair<int,int> > V[N]; // وزن و شماره راس‌هایی که به آن یال دارد
bool find_mst(){
	fill_n(min_e,n,INF); // مقدار دهی اولیه
	fill_n(sel_e,n,-1);  // مقدار دهی اولیه
	fill_n(used,n,false);  // مقدار دهی اولیه
	min_e[0]=0;	 // صفر قرار می‌دهیم تا ابتدا راس صفر(یک) انتخاب شود
	set < pair<int,int> > q; // داده‌ساختاری که فاصله هر راسی که به مجومه انتخاب شده راه دارد را نگه می‌دارد
	q.insert (make_pair (0, 0)); 
	for (int i=0; i<n; ++i) {
		if (q.empty()) 
			return false;
		int v = q.begin()->second; // کوچک‌ترین عضو یعنی نزدیک‌ترین عضو است set عضو ابتدایی
		q.erase (q.begin());
 
		if (sel_e[v] != -1)
			ans.push_back(make_pair(sel_e[v],v));
 
		for (int j=0; j<V[v].size(); j++) {
			int to = V[v][j].first,
				cost = V[v][j].second;
			if (cost < min_e[to]) {
				q.erase (make_pair (min_e[to], to));
				min_e[to] = cost;
				sel_e[to] = v;
				q.insert (make_pair (min_e[to], to));
			}
 		}
	}
}
 
int main() {	
	cin >> n>>m;
	for(int i=0; i<m; i++){ // حلقه گرفتن یال‌ها
		int a,b,w;
		cin >>a>>b>>w; // به ترتیب ۲ راس و سپس وزن یال
		V[a-1].push_back(make_pair(b-1,w)); // است n-1 یکی کم می‌کنیم چون بازه‌ی معتبر ما صفر تا
		V[b-1].push_back(make_pair(a-1,w)); // است n-1 یکی کم می‌کنیم چون بازه‌ی معتبر ما صفر تا
	}
	if(find_mst()==false)
		cout << "No MST!\n";
}

• الگوریتم پریم - سایت ماکزیمال