خوارزميات التجول على البيان Graph traversal algorithms و مقارنة بين البحث بالعمق أولاً و البحث بالعرض أولاً

تعتبر كل من خوارزميتي البحث بالعمق أولاً DFS و البحث بالعرض أولاً BFS من خوارزميات التجوال في بنى المعطيات الشجرية Trees و البيان Graphs.

حيث يتم تحديد عقدة الجذر للبيان و من ثم تعمل الخوارزمية المختارة على المرور على جميع العقد NODES في هذا البيان.

ليكن لدينا البيان التالي والذي له العقدة 1 كجذر له root node:

تقوم خوارزمية BFS البحث بالعرض بطباعة معلومات كل مستوى من البيان على حدى حيث أن المستوى يمثل مجموعة العقد التي لها نفس البعد عن العنصر الجذر أي تقوم بالمرور على الجذر 1 أولاً ثم للمستوى التالي 2 و 3 ( وهما أبناء الجذر  ولهم بعد 1 عن الجذر )، ثم 4 و 5 في المستوى التالي.. وهكذا.

أما خوارزمية DFS تبحث بالعمق، أي تأخذ عقدة، ثم تنتقل لأحد أولادها، ثم أحد أولاد العقدة الجديدة و تكرر هذا حتى تصل إلى ورقة (عقدة خارجية ليس لها أبناء) و بعد طباعة رقم العقدة الورقة تقوم بالتراجع لأب هذه العقدة ثم تنتقل لابنه الثاني و تستمر بالمرور ابن تاو الآخر حتى تصل إلى ورقة و هكذا حتى تنتهي من عقدة ما، فتعود لأبيها.. ثم لأبيها و من ثم يمكن أن تنتهي من أحد أفرع الشجرة و تنتقل للجذر ثم للفرع الآخر و هكذا، أي ضمن المثال، سوف تطبع 1 ثم ابنها 2 ثم ابنها 4 ثم تعود ل 2 و تنتقل لابنها الآخر 5 و عند انتهاء الأولاد تعود ل 2 ثم تعود ل 1 ثم تنتقل للفرع الآخر أو الابن الآخر للجذر والذي هو  3 فنزوره و لا تجد أبناء فتعود للجذر و تنتهي. لها 3 أنماط مرور موجودة في الصورة المثال.

تحوي المقالة التالية على شرح و أمثلة لكلا الخوارزميتين. 

و للتعرف على كيفية تمثيل بنية المعطيات يمكنك قراءة المقالة:

بالإضافة إلى شرح وائل يمكنك التفكير في الفرق بين الخوارزميتين عبر المكدسstack والطابور queue

حيث يمكننا تمثيل خوارزمية البحث بالعمق وكأنها على هيئة مكدس حيث تعمل بتقنية LIFO حيث لو اعتبرنا لدينا العقد التالية 

{
a:[b,c],
b:[d],
d:[f],
f:[]
}

حيث كل مفتاح في القائمة السابقة يمثل عقدة والمصفوفة المرافقة للمفتاح تُمثل العقد المُتصلة بتلك العقدة

لو قمنا بتطبيق االبحث بعمق سنلاحظ أننا نقوم بالدخول إلى العقدة a, ثم ندخل بعدها العقدة b فيصبح شكل المكدس لدينا a,b وبما أن b في أعلى المكدس فنقوم بإستكمال العمليات على b فندخل إلى العقدة d فتصبح بالتالي d في قمة المكدس فندخل إلى f فتصبح في قمة المكدس فندخل إليها نجد نهاية فارغة فنرجع إلى العنصر السابق في المدس نجده a فنستكمل العمليات عليه وندخل إلى c

فيصبح بالتالي ترتيب العناصر لدينا 

a,b,d,f,c

بينما عند إستخدام البحث بالعرض يكون الأمر كأننا إستخدمنا طابور queue فنعمل بتقنية الFIFO أي أن العنصر الذي يدخل أولًا نقوم بإستكمال العمليات عليه ومن ثم نرى العنصر الذي دخل بعده

في حالتنا هنا نقوم بالدخول إلى العنصر a ومن ثم نقوم بإدخال العنصر b إلى الطابور ولكن نستكمل العمليات على العنصر a فنقوم بإدخال العنصر c بعدها نقوم بالدخول إلى العنصر التالي في الطابور وهو العنصر b فنقوم بإدخال العنصر d في الطابور ولكن لا نقوم بعمليات عليه وإنما نقوم بالعمليات على العنصرc لأنه سابق الدور في الطابور 

فبإختصار في حالة البحث بعمق نقوم بالمرور على جميع العقد التي نقابلها على عكس البحث بعرض نقوم بالمرور على العقد بالترتيب