بحث بتفضيل التوسع
المحتويات

على سبيل التعريف، يُشير مصطلح بحث العرض أولا أو البحث أفقي الأولوية إلى خوازمية لبحث الرسوم البيانية، يتم فيها المرور الممنهج على العقد في كل مستوى قبل الانتقال إلى المستوى الذي يليه. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
الخصائص والتطبيقات
في هذا الإطار، تشكل الحواف التي تم عبورها بواسطة BFS شجرة مسارات أقصر مسافات بين رأس الانطلاق (و هو جذر الشجرة) وجميع الرؤوس الأخرى في (G(V،E. المسافة هنا تقدّر بعدد الحواف التي تكوّن المسار.
من جهة ثانية، يصلح استعمال BFS في كل بيان بغض النظر سواء كان البيان موجها أم لا
الكشف عن حلقة في بيان موجه (G(V،A
من جانب آخر، لخوارزمية BFS الكثير من التطبيقات، أغلبها كروتين أولية في الخوارزميات ذات أكثر تعقيد المألوفة في نظرية البيانات والتدفق في الشبكات، والأكثر استخداما من بينها هي:
إضافةً إلى ذلك، عدد المكونات المتصلة في البيان (G(V،E هو عدد مرات تنفيذ الحلقة الخارجية «طال ما علامة رأس v هي 0» في الخوارزنية
كيفية العمل
خوارزمية BFS
تعاد هذه العملية لكل المكونات المتصلة في البيان (G(V،E
علاوةً على ذلك، في كل تكرار تتم زيارة موجة من الرؤوس متساوية المسافة من v ، ونرى أنها تنتشر خلال العملية، حتى يتم زيارة جميع الرؤوس في البيان التي يمكن الوصول إليها من v.
وفي هذا الصدد، بدءًا من أي رأس (v∈V(G ، تتم زيارة جميع الرؤوس المجاورة لالرأس v أولاً، ثم الرؤوس المجاورة لكل من الرؤوس المجاورة لالرأس v ، أي الرؤوس على مسافة حافتين نسبة إلى v ، وهلم جرا.
وعلى صعيد آخر، لكي يكون ترتيب زيارة الرؤس متسقًا مع وصفها النظري، فإن خوارزمية BFS عبارة عن مخطط تكراري مبني حول طابور Q ، يمثل البنية البيانية المركزية للانغراز العملي للخوارزمية، وهي نظريّا مجموعة مرتّبة يتم فيها إدخال العناصر من «الذيل» ونزعها من «الرأس»، وبهذا الشكل أوّل عنصر يضاف إلى Q هو أول من يخرج منها مع حفاظ ترتيب كل العناصر الموجودة في القائمة.
{Q ← Q ∪ {v
- طالما Q ليست فارغة (Q ≠ φ)
- لجميع الرؤوس ui المجاورة لـ v0 وهو الرأس الأول في Q
- إذا ui له علامة 0
- C ← علامة ui
- 1+C ← C
- ضف (vo،ui) إلى قائمة الحواف A
- {Q ← Q ∪ {ui
- نهاية إذا
نهاية لجميع
- {Q ← Q - {v0 (حدف الرأس الأول من الطابور Q)
- نهاية طالما
- نهاية طالما
ضع علامة 0 على كل رؤوس (G(V،E
- قائمة الحواف A ← φ (مجموعة فارغة)
- طابور الزيارات Q ← φ (مجموعة فارغة)
- C ← 1
- طالما علامة رأس v هي 0
- C ← علامة الرأس v
- 1+C ← C
اختبار استوائبة البيان (G(V،E
كذلك، خوارزميات اختبار الوصول أو مسألة المجاورة المتعدية ، وهي امكانية الانتقال من رأس إلى آخر في البيان عبر الحواف الموجودة
- انظر كذلك
- بحث بتفضيل العمق
- بحث شعاعي
- بحث بتفضيل الأولوية
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟