چوڑائی اول تلاش
From Wikipedia, the free encyclopedia
ریاضی کی شاخ نظریۂ گراف میں درخت کے راس پر سفر کرنے یا تلاش کرنے کا الخوارزم ہے۔ گراف پر تلاش کے لیے بھی استعمال ہو سکتا ہے، جس کے لیے گراف کا عبری درخت استعمال کیا جا سکتا ہے۔ درخت کو عموماً اس طرح بنایا جاتا ہے کہ کوئی قمہ "جڑ" معلوم ہو۔ اس طریقہ میں درخت کی "جڑ" سے شروع کر کے زیادہ سے زیادہ چوڑائ کی جانب راس کے ہمسایہ راس پر سفر (تلاش) کیا جاتا ہے اور گہرائ کی طرف اسی وقت قدم اُٹھایا جاتا ہے جب چوڑائ کی جانب قدم اُٹھانا ممکن نہ ہو۔
اصطلاح | term |
---|---|
گراف |
graph |
مثلاً تصویر میں جڑ 1 سے شروع کرتے ہوئے اس کے ہمسایہ 2، 3، 4، پر گئے۔ جس قمہ پہلی دفعہ پر جاؤ اس پر عددی لصق لگا دو۔ اب چوڑائی میں مزید جانا ممکن نہ تھا، اس لیے گہرائی کی طرف قدم لیتے ہوئے 5 پر گئے اور پھر چوڑائی میں 6، 7، 8۔ اس طرح چلتے رہو جب تک تمام راس پر لصق لگ جائیں۔