TechCodeview

في هذه المقالة، سنناقش خوارزمية كروسكال. هنا، سنرى أيضًا مدى تعقيد خوارزمية كروسكال وعملها ومثالها وتنفيذها.

ولكن قبل الانتقال مباشرة نحو الخوارزمية، يجب علينا أولاً فهم المصطلحات الأساسية مثل الشجرة الممتدة والحد الأدنى من الشجرة الممتدة.

تمتد شجرة - الشجرة الممتدة هي رسم بياني فرعي لرسم بياني متصل غير موجه.

الحد الأدنى الشجرة الممتدة - يمكن تعريف الحد الأدنى من الشجرة الممتدة على أنها الشجرة الممتدة التي يكون فيها مجموع أوزان الحافة هو الحد الأدنى. وزن الشجرة الممتدة هو مجموع الأوزان الممنوحة لحواف الشجرة الممتدة.

والآن لنبدأ بالموضوع الرئيسي.

خوارزمية كروسكال يتم استخدامه للعثور على الحد الأدنى من الشجرة الممتدة للرسم البياني الموزون المتصل. الهدف الرئيسي للخوارزمية هو العثور على مجموعة فرعية من الحواف التي يمكننا من خلالها اجتياز كل قمة في الرسم البياني. إنه يتبع النهج الجشع الذي يجد الحل الأمثل في كل مرحلة بدلاً من التركيز على الحل الأمثل العالمي.

كيف تعمل خوارزمية كروسكال؟

في خوارزمية كروسكال، نبدأ من الحواف ذات الوزن الأقل ونستمر في إضافة الحواف حتى الوصول إلى الهدف. يتم سرد خطوات تنفيذ خوارزمية كروسكال على النحو التالي -

• أولاً، قم بفرز جميع الحواف من الوزن المنخفض إلى الوزن العالي.
• الآن، خذ الحافة ذات الوزن الأقل وأضفها إلى الشجرة الممتدة. إذا كانت الحافة المراد إضافتها تخلق دورة، فارفض الحافة.
• استمر في إضافة الحواف حتى نصل إلى جميع القمم، ويتم إنشاء الحد الأدنى من الشجرة الممتدة.

تطبيقات خوارزمية كروسكال هي -

• يمكن استخدام خوارزمية كروسكال لتخطيط الأسلاك الكهربائية بين المدن.
• ويمكن استخدامه لوضع اتصالات LAN.

مثال على خوارزمية كروسكال

الآن، دعونا نرى عمل خوارزمية كروسكال باستخدام مثال. سيكون من الأسهل فهم خوارزمية كروسكال باستخدام مثال.

لنفترض أن الرسم البياني المرجح هو -

وزن حواف الرسم البياني أعلاه موضح في الجدول أدناه -

الآن، قم بفرز الحواف المذكورة أعلاه بالترتيب التصاعدي لأوزانها.

لنبدأ الآن في إنشاء الحد الأدنى من الشجرة الممتدة.

عمل الكمبيوتر

الخطوة 1 - أولا، أضف الحافة أ.ب مع الوزن 1 إلى MST.

الخطوة 2 - أضف الحافة ل مع الوزن 2 إلى MST لأنه لا يقوم بإنشاء الدورة.

الخطوه 3 - أضف الحافة قبل الميلاد مع الوزن 3 إلى MST، لأنه لا يقوم بإنشاء أي دورة أو حلقة.

الخطوة 4 - الآن، اختر الحافة قرص مضغوط مع الوزن 4 إلى MST، لأنها لا تشكل الدورة.

الخطوة 5 - بعد ذلك، اختر الحافة لكن مع الوزن 5. سيؤدي تضمين هذه الحافة إلى إنشاء الدورة، لذا تخلص منها.

الخطوة 6 - اختر الحافة تكييف مع الوزن 7. سيؤدي تضمين هذه الحافة إلى إنشاء الدورة، لذا تخلص منها.

الخطوة 7 - اختر الحافة إعلان مع الوزن 10. سيؤدي تضمين هذه الحافة أيضًا إلى إنشاء الدورة، لذا تخلص منها.

لذا، فإن الحد الأدنى النهائي للشجرة الممتدة التي تم الحصول عليها من الرسم البياني الموزون المحدد باستخدام خوارزمية كروسكال هو -

تكلفة MST هي = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

الآن، عدد الحواف في الشجرة أعلاه يساوي عدد القمم ناقص 1. لذا، تتوقف الخوارزمية هنا.

خوارزمية

 Step 1: Create a forest F in such a way that every vertex of the graph is a separate tree. Step 2: Create a set E that contains all the edges of the graph. Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning Step 4: Remove an edge from E with minimum weight Step 5: IF the edge obtained in Step 4 connects two different trees, then add it to the forest F (for combining two trees into one tree). ELSE Discard the edge Step 6: END 

تعقيد خوارزمية كروسكال

الآن، دعونا نرى التعقيد الزمني لخوارزمية كروسكال.

تعقيد الوقت
التعقيد الزمني لخوارزمية كروسكال هو O(E logE) أو O(V logV)، حيث E هو الرقم. من الحواف، وV هو لا. من القمم.

تنفيذ خوارزمية كروسكال

الآن، دعونا نرى تنفيذ خوارزمية كروسكال.

برنامج: اكتب برنامجًا لتنفيذ خوارزمية kruskal في لغة C++.

 #include #include using namespace std; const int MAX = 1e4 + 5; int id[MAX], nodes, edges; pair <long long, pair> p[MAX]; void init() { for(int i = 0;i <max;++i) id[i]="i;" } int root(int x) { while(id[x] !="x)" id[x]="id[id[x]];" x="id[x];" return x; void union1(int x, y) p="root(x);" q="root(y);" id[p]="id[q];" long kruskal(pair<long long, pair> p[]) { int x, y; long long cost, minimumCost = 0; for(int i = 0;i <edges;++i) { x="p[i].second.first;" y="p[i].second.second;" cost="p[i].first;" if(root(x) !="root(y))" minimumcost +="cost;" union1(x, y); } return minimumcost; int main() x, y; long weight, cost, init(); cout <> nodes &gt;&gt; edges; for(int i = 0;i <edges;++i) { cout<> x &gt;&gt; y &gt;&gt; weight; p[i] = make_pair(weight, make_pair(x, y)); } sort(p, p + edges); minimumCost = kruskal(p); cout &lt;<'minimum cost is '<< minimumcost << endl; return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/kruskals-algorithm-6.webp" alt="Kruskal"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></'minimum></edges;++i)></edges;++i)></max;++i)></long>