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

===== تعریف =====

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

===== الگوریتم =====
==== شرح ====
{{:آموزش:الگوریتم:mst_kruskal_small.gif |}}
در این الگوریتم، یال‌ها را بر اساس وزن به صورت صعودی مرتب می‌کنیم. سپس از اولین یال شروع می‌کنیم و هر یالی که با یال‌هایی که قبلا انتخاب کردیم دور نمی‌سازد را انتخاب می‌کنیم. تا جایی که درخت تشکیل شود.

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

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

در شکل یک مثال برای اجرای این الگوریتم را می‌بینید. توجه کنید یال‌های انتخاب شده تنها در آخر کار یک مجموعه‌ی همبند تشکیل می‌دهند ولی در الگوریتم پریم همیشه در طول ساخت درخت، مجموعه ما همبند بود.
==== صحت ====
فرض خلف: فرض کنید درخت پوشای کمینه‌ی $T$ وجود دارد که مجموع‌ وزن یال‌های ساخته شده توسط آن کمتر از درخت تولید شده توسط الگوریتم کروسکال به نام $G$ باشد. کم‌ورن‌ترین یالی در که عضو  $T$ است ولی عضو  $G$ نیست را انتخاب کنید. این یال حتما توسط الگوریتم کروسکال انتخاب می‌شد مگر اینکه با یال‌های قبلی دور بسازد و چون تمام یال های سبک تر از این یال در هر دو درخت وجود دارد به معنی آن است که در درخت $T$ دور وجود دارد که تناقض است.
===== شبه کد =====
  - تمام یال‌ها را به ترتیب صعودی وزن مرتب کن
  - برای هر راس v یک مجموعه بساز.
  - یال (u,v) را انتخاب کن.
  - اگر مجموعه‌ی u و v یکی نیستند. کارهای زیر را انجام بده.
      -  مجموعه‌ی آنها را ادغام کن.
      -  یال (u,v) را به عنوان یالی از درخت پوشای کمینه بردار.
  - اگر هنوز n-1 یال انتخاب نشده به شماره ۳ برو.
  - پایان

===== پیچیدگی‌ الگوریتم =====
مرتب کردن یال ها و بررسی یال‌ها از  $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)$ است.

<code c++ 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();	
	
}
</code>
[[تعریف و ویژگی‌های درخت پوشای کمینه|درخت پوشای کمینه]] در پشته MST ریخنه می‌شود. می‌توانید بر حسب نیاز به جای اینکار مجموع وزن یال‌های درخت را نگه دارید یا همراه با یال‌ها وزنشان را هم نگه دارید.


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

<code c++ 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();	

	
}
</code>

===== مراجع =====

  * [[http://e-maxx.ru/algo/mst_kruskal|الگوریتم کروسکال - سایت ماکزیمال]]
  * [[http://e-maxx.ru/algo/mst_kruskal_with_dsu|الگوریتم کروسکال با مجموعه‌های مجزا - سایت ماکزیمال]]  
  * [[http://en.wikipedia.org/wiki/Kruskal%27s_algorithm|الگوریتم کروسکال - ویکی‌پدیا]]