الدرس الثاني

يقوم الدرس على خوارزميات البحث في المخططات، وتحديداً خوارزمية البحث بأولوية الاتساع وخوارزمية البحث بأولوية العمق. تعتمد الأولى على استكشاف العقد بحسب المستوى تلو الآخر باستخدام هيكل بيانات الطابور، حيث تفحص العقد المجاورة والأشقاء قبل الانتقال إلى الفروع العميقة، وتستخدم في شبكات النظر للظير والبث الشبكي. بينما تعتمد الثانية على التعمق في المخطط باتباع الحواف واستخدام هيكل بيانات المكدس، حيث تتجه البحث إلى قاع الشجرة الفرعية قبل التراجع وفحص الأشقاء، وتستخدم في حل المتاهات وإيجاد المسارات. مثال سريع: لو كان لديك مخطط يبدأ بالعقدة A وتتفرع منها B وC، فإن خوارزمية الاتساع تفحص A ثم تفحص B وC قبل النزول للمستوى التالي، بينما خوارزمية العمق تفحص A ثم تذهب مباشرة لتعميق البحث في فرع B حتى نهايته قبل العودة لـ C.

الفكرة الأساسية

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

الشرح

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

مثال محلول خطوة بخطوة

خذ مخططاً يبدأ بالعقدة الجذرية A، وتتفرع منها العقدتان B وC في المستوى الأول، وتتفرع من B العقدتان D وE، وتتفرع من C العقدة F. لتطبيق خوارزمية البحث بأولوية الاتساع للوصول إلى F من A:

1. ابدأ بالعقدة الجذرية A وأضفها إلى الطابور.
2. احذف العقدة الجذرية A من الطابور لمعالجتها، ثم أضف فروعها إلى الطابور وهما العقدتان B وC.
3. احذف العقدة B من مقدمة الطابور لمعالجتها، ثم أضف فروعها وهما العقدتان D وE إلى الطابور.
4. احذف العقدة C وعالجاتها، ثم أضف فرعها F إليها.
5. احذف العقدة D وعالجاتها وليس لديها فروع.
6. احذف العقدة E وعالجاتها وليس لديها فروع.
7. احذف العقدة F لمعالجتها وبذلك أصبح الطابور فارغاً وانتهت عملية البحث. العقد التي فحصت هي A ثم B ثم C ثم D ثم E ثم F.

أخطاء شائعة

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

سؤالان للتدريب مع الإجابة

السؤال الأول: ما هيكل البيانات المستخدم لتتبع الموقع التالي لفحصه في خوارزمية البحث بأولوية الاتساع؟ الإجابة: هيكل بيانات الطابور. السؤال الثاني: أي الخوارزميتين تفضل استخدامها عندما يكون هيكل المخطط واسعاً وقصيراً؟ الإجابة: خوارزمية البحث بأولوية الاتساع.