Minimum spanning tree

ریاضی کی شاخ نظریۂ گراف میں وزن شدہ گراف کا ایسا مدیدی درخت جس کا وزن کم سے کم ہو، کو صغیر مدیدی درخت کہا جاتا ہے۔ اس کو صغیر وصیلہ بھی کہا جاتا ہے۔ فرض کرو کہ ہمیں مختلف علاقوں میں قائم برقی بجلی گھروں کو تاریں بچھا کر ملانا ہے۔ یہ بجلی گھر گراف کے راس ہوں گے۔ دو بجلی گھروں کو ملانے کا خرچ ان راس کے درمیان کنارے کا وزن ہے۔ کچھ علاقوں کو ملانا جغرافیائی یا سیاسی اعتبار سے مہنگا یا ناممکن ہو سکتا ہے۔ اس کا سستہ تریں حل مطلوب ہے جو "صغیر وصیلہ" ہے۔

لالچی الخوارزم 
کسی گراف کا صغیر مدیدی درخت نکالنے کا مشہور الخوارزم کرُسکال (Kruskal) نے پیش کیا جو ایک لالچی الخوارزم ہے۔ اسے لالچی اس لیے کہتے ہیں کیونکہ یہ ہر مرحلہ پر کم ترین خرچہ والی صورت کا انتخاب کرتا ہے، بغیر دیکھے کہ اس کا دوسری جگہوں پر کیا اثر ہو گا۔ ہر مرحلہ پر کم از کم وزن والے کنارے کا انتخاب کیا جاتا ہے بشرطیکہ اس انتخاب سے اب تک بننے والے درخت میں دورہ نہ بنتا ہو۔ اس الخوارزم کو ہم مثال کے ذریعہ واضح کرتے ہیں :

مزید دیکھیے

بیرونی روابط 
 
کامنز زمرہ جس کا ربط ویکی ڈیٹا پر ہے
Short description is different from Wikidata