هذه المقالة يتيمة. ساعد بإضافة وصلة إليها في مقالة متعلقة بها
يرجى مراجعة هذه المقالة وإزالة وسم المقالات غير المراجعة، ووسمها بوسوم الصيانة المناسبة.

البحث المتسع الاول

من ويكيبيديا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث
N write.svg
تعرَّف على طريقة التعامل مع هذه المسألة من أجل إزالة هذا القالب.هذه مقالة غير مراجعة. ينبغي أن يزال هذا القالب بعد أن يراجعها محرر مغاير للذي أنشأها؛ إذا لزم الأمر فيجب أن توسم المقالة بقوالب الصيانة المناسبة. يمكن أيضاً تقديم طلب لمراجعة المقالة في الصفحة المُخصصة لذلك. (يونيو 2019)

البحث المتسع الأول أو البحث المتوسع و المسمى أيضا خوارزمية BFS[1] هي العملية التي تقوم بالمرور المنهجي من جميع الرؤوس في بيان (G(V،E و ترقيمها حسب ترتيب الزيارة، عبورا بالحواف الموجودة داخل المكونات المتصلة للبيان . تتم زيارة كل رأس في (G(V،E مرة واحدة.

كيفية العمل[عدل]

بدءًا من أي رأس (v∈V(G ، تتم زيارة جميع الرؤوس المجاورة لالرأس v أولاً، ثم الرؤوس المجاورة لكل من الرؤوس المجاورة لالرأس v ، أي الرؤوس على مسافة حافتين نسبة إلى v ، وهلم جرا.

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

في كل تكرار تتم زيارة موجة من الرؤوس متساوية المسافة من v ، ونرى أنها تنتشر خلال العملية، حتى يتم زيارة جميع الرؤوس في البيان التي يمكن الوصول إليها من v.

تعاد هذه العملية لكل المكونات المتصلة في البيان (G(V،E

خوارزمية BFS[عدل]

Breadth first search tree.jpg
ضع علامة 0 على كل رؤوس (G(V،E
قائمة الحواف A ← φ (مجموعة فارغة)
طابور الزيارات Q ← φ (مجموعة فارغة)
C ← 1
طالما علامة رأس v هي 0
C ← علامة الرأس v
1+C ← C
{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)
نهاية طالما
نهاية طالما

الخصائص والتطبيقات[عدل]

  • عدد المكونات المتصلة في البيان (G(V،E هو عدد مرات تنفيذ الحلقة الخارجية "طال ما علامة رأس v هي 0" في الخوارزنية
  • يصلح استعمال BFS في كل بيان بغض النظر سواء كان البيان موجها أم لا
  • تشكل الحواف التي تم عبورها بواسطة BFS شجرة مسارات أقصر مسافات بين رأس الانطلاق (و هو جذر الشجرة) وجميع الرؤوس الأخرى في (G(V،E. المسافة هنا تقدّر بعدد الحواف التي تكوّن المسار.

لخوارزمية BFS العديد من التطبيقات، معظمها كروتين أولية في الخوارزميات ذات أكثر تعقيد المألوفة في نظرية البيانات والتدفق في الشبكات، والأكثر استخداما من بينها هي :

  • الكشف عن حلقة في بيان موجه (G(V،A
  • اختبار استوائبة البيان (G(V،E[2]
  • خوارزميات اختبار الوصول أو مسألة المجاورة المتعدية[3] ، و هي امكانية الانتقال من رأس إلى آخر في البيان عبر الحواف الموجودة

انظر أيضا[عدل]

مراجع[عدل]

  1. ^ TARJAN, Robert Endre. Data structures and network algorithms. Siam, 1983.
  2. ^ HOPCROFT, John et TARJAN, Robert. Efficient planarity testing. Journal of the ACM (JACM), 1974, vol. 21, no 4, p. 549-568.
  3. ^ AHO, Alfred V. , GAREY, Michael R., et ULLMAN, Jeffrey D. The transitive reduction of a directed graph. SIAM Journal on Computing, 1972, vol. 1, no 2, p. 131-137.