گہرائی اول تلاش

(Depth-first search سے رجوع مکرر)

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

ترتیب جس میں راس پھیلائے جاتے ہیں
ترتیب جس میں راس پھیلائے جاتے ہیں
اصطلاح term

گراف
راس
کنارہ
درخت
عبری
دورہ
شاخ
جڑ

graph
vertex, vertices
edge
tree
spanning
cycle
branch
root

مثلاً تصویر میں جڑ 1 سے شروع کیا اور گہرائی کی جانب 2، 3، 4، پر چلے گئے۔ جس قمہ پر جاؤ وہاں عدد لصق لگاتے جاؤ۔ قمہ 4 سے مزید گہرا جانا ممکن نہ تھا، اس لیے ایک قدم واپس 3 پر آئے اور پھر گہرائ میں 5 پر اُتر گئے۔ اس کے بعد دو قدم واپس 2 پر آنا پڑا (کیونکہ 3 سے کسی نئے قمہ پر جانا ممکن نہ تھا)۔ اس طرح یہ سلسلہ جاری رکھا جب تک تمام راس کا گُزر نہیں ہو گیا۔

مزید دیکھیے

ترمیم

==بیرونی روابط ==*

E=mc2     اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں LTR پڑھیٔے     ریاضی علامات