الگوریتم کروسکال

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

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

اما چگونه متوجه شویم که یال جدید با یال‌های انتخابی قبلی دور نمی‌سازد؟ کافیست گرافی که تا کنون از یال‌های انتخابی تشکیل شده را به مؤلفه‌های همبندی تقسیم کنیم و اگر یال جدید هر دو سر آن در یک مؤلفه بود، یال جدید دور ایجاد می‌کند و در غیر اینصورت اضافه کردن یال جدید مشکلی ندارد.

هر راس متغیری همراه خود دارد که شماره مولفه‌ی همبندیش را نشان می‌دهد. در ابتدا هر راس، خود یک مؤلفه‌ی همبندیست. و وقتی یک یال بین دو مؤلفه ارتباط ایجاد می‌کند باید شماره مولفه‌ی همبندی هر دو گروه یکی شود.

در شکل یک مثال برای اجرای این الگوریتم را می‌بینید. توجه کنید یال‌های انتخاب شده تنها در آخر کار یک مجموعه‌ی همبند تشکیل می‌دهند ولی در الگوریتم پریم همیشه در طول ساخت درخت، مجموعه ما همبند بود.

فرض خلف: فرض کنید درخت پوشای کمینه‌ی $T$ وجود دارد که مجموع‌ وزن یال‌های ساخته شده توسط آن کمتر از درخت تولید شده توسط الگوریتم کروسکال به نام $G$ باشد. کم‌ورن‌ترین یالی در که عضو $T$ است ولی عضو $G$ نیست را انتخاب کنید. این یال حتما توسط الگوریتم کروسکال انتخاب می‌شد مگر اینکه با یال‌های قبلی دور بسازد و چون تمام یال های سبک تر از این یال در هر دو درخت وجود دارد به معنی آن است که در درخت $T$ دور وجود دارد که تناقض است.

1. تمام یال‌ها را به ترتیب صعودی وزن مرتب کن
2. برای هر راس v یک مجموعه بساز.
3. یال (u,v) را انتخاب کن.
4. اگر مجموعه‌ی u و v یکی نیستند. کارهای زیر را انجام بده.
   1. مجموعه‌ی آنها را ادغام کن.
   2. یال (u,v) را به عنوان یالی از درخت پوشای کمینه بردار.
5. اگر هنوز n-1 یال انتخاب نشده به شماره ۳ برو.
6. پایان

مرتب کردن یال ها و بررسی یال‌ها از $O(m+m log n)$ است که برابر $O(m log n)$ است و هر‌بار اتصال دو مولفه از $O(n)$ است که چون اتصال $n-1$ بار انجام می‌شود پیچیدگی الگوریتم $O(m log n + n^2)$ می‌شود

همانطور که گفته شده پیچیدگی این پیاده‌سازی از $O(m log n + n^2)$ است.

Kruskal.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N=1000; // حداکثر تعداد راس ها
int n,m;
vector <pair <int, pair <int, int> > > g; // پشته شامل یال و وزن ‌انها
vector <pair <int, int> > MST; // پشته‌ای که  در آن درخت پوشای کمینه را خواهیم ریخت
int tree_ID [N]; // شماره مولفه‌همبندی هر راس
void find_mst(){
	sort (g.begin (), g.end ());
	MST.clear();
	for(int i=0; i<n; i++)
	    tree_ID[i]=i;
	for(int i=0; i<m; i++){
		int f=g[i].second.first;
		int t=g[i].second.second;
		if(tree_ID[f]!=tree_ID[t]){ 
		    MST.push_back(g[i].second);
			int old_ID = tree_ID [t], new_ID = tree_ID [f];
			for(int j=0; j<n; j++) // یکی کردن شماره‌مولفه همبندی ها برای ادغام دو مجموعه
				if (tree_ID [j] == old_ID)
					tree_ID [j] = new_ID;
		}
	}
}
 
int main() {
	cin >> n>>m;
	g.clear();
	for(int i=0; i<m; i++){
		int f,t,w;
		cin >>f>>t>>w;
		g.push_back(make_pair (w, make_pair (--f, --t)));
                /* 
                * است n است ولی بازه معتبر راس ها در ورودی ۱ تا n-۱ بازه معتبر راس ها برای ما صفر تا 
                * پس ما باید قبل از ذخیره یکی از آنها کم کنیم
                */
	}
    find_mst();	
 
}

درخت پوشای کمینه در پشته MST ریخنه می‌شود. می‌توانید بر حسب نیاز به جای اینکار مجموع وزن یال‌های درخت را نگه دارید یا همراه با یال‌ها وزنشان را هم نگه دارید.

می‌توان از داده‌ساختار مجموعه‌های مجزا برای مولفه‌های همبندی استفده کرد، در این صورت پیچیدگی الگوریتم به $O(m log n + n)$ که برابر $O(m log n)$ است کاهش پیدا می‌کند.

efficient_Kruskal.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N=1000;
int n,m;
vector <pair <int, pair <int, int>>> g; // پشته شامل یال و وزن ‌انها
vector <pair <int, int>> MST; // پشته‌ای که  در آن درخت پوشای کمینه را خواهیم ریخت
int parent [N];
 
int root (int a){ // هر مولفه‌ یک ریشه دارد که نماد آن است
    if(parent[a] ==a)
        return a;
    parent[a]=root(parent[a]);
    return root(parent[a]);
}
 
void Union (int a,int b){ // تابع ادغام
    parent[root(a)]=root(b);
}
 
void find_mst(){
	sort (g.begin (), g.end ());
	MST.clear();
	for(int i=0; i<n; i++)
	    parent[i]=i;
	for(int i=0; i<m; i++){
		int f=g[i].second.first;
		int t=g[i].second.second;
		if(root(f)!=root(t)){
		    MST.push_back(g[i].second);
			Union(f,t);
		}
	}
}
 
int main() {
	cin >> n>>m;
	g.clear();
	for(int i=0; i<m; i++){
		int f,t,w;
		cin >>f>>t>>w;
		g.push_back(make_pair (w, make_pair (--f, --t)));
                /* 
                * است n است ولی بازه معتبر راس ها در ورودی ۱ تا n-۱ بازه معتبر راس ها برای ما صفر تا 
                * پس ما باید قبل از ذخیره یکی از آنها کم کنیم
                */
	}
 
    find_mst();	
 
 
}

• الگوریتم کروسکال - سایت ماکزیمال
• الگوریتم کروسکال با مجموعه‌های مجزا - سایت ماکزیمال
• الگوریتم کروسکال - ویکی‌پدیا