آموزش:الگوریتم:الگوریتم کروسکال [المپدیـا]

فهرست مندرجات

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

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

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

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

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

فرض خلف: الگوریتم وزن فرض کنید درخت پوشای کمـینـه‌ی $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)$ است.

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(); }