BFS - اتساع ووك


اتساع البحث الأول ( BFS )
BFS & nbsp؛ (بحث العرض أولاً ، بحث العرض أولاً ) - طريقة مسح الرسم البياني ، تُستخدم غالبًا في كل من الخوارزميات البسيطة والمتقدمة. يعمل بحث Breadth-First عن طريق التنقل خلال المستويات الفردية للرسم البياني ، بدءًا من العقدة المصدر والانتقال تدريجياً بعيدًا عنها. يظهر هذا بوضوح في الرسوم المتحركة.
لكتابة أبسط BFS & nbsp؛ ، يجب أن تكون قادرًا على العمل بهيكل بيانات يسمح لك بأخذها من البداية & nbsp ؛ ووضعها حتى النهاية ، وأيضًا أن تكون قادرًا على التخزين الرسم البياني في شكل قائمة مجاورة (أي مع قائمة انتظار).
نبسب ؛
وصف رسمي للخوارزمية
1) ضع رقم الرأس الذي يبدأ منه البحث في قائمة الانتظار الفارغة في البداية.
2) قم باستخراج قمة الرأس U من بداية قائمة الانتظار وتمييزها على أنها مستخدمة في مصفوفة منفصلة.
3) في نهاية قائمة الانتظار ، أضف جميع الرؤوس & nbsp ؛ التي يمكننا الوصول إليها & nbsp ؛ باستخدام الحافة من الرأس U ، & nbsp ؛ والتي لم يتم تصنيفها بعد.
4) إذا كانت قائمة الانتظار فارغة ، فهذا يعني أنه تم فحص جميع عقد الرسم البياني المتصل ، وإلا فارجع إلى الخطوة 2.
نبسب ؛
التعقيد
نظرًا لأن الخوارزمية تزور جميع عُقد الرسم البياني في أسوأ الحالات ، عند تخزين الرسم البياني كقوائم مجاورة ، & nbsp ؛ التعقيد الزمني للخوارزمية هو O (| V | + | E |) ، حيث V هي مجموعة رؤوس الرسم البياني ، و E هي مجموعة الحواف. & nbsp ؛ بمعنى آخر ، تعمل الخوارزمية في أسوأ حالة لرقم عدد الأضلاع + عدد الرؤوس .
نبسب ؛

Training problem

BFS: البداية (C ++)

BFS (بحث العرض أولاً) هو طريقة مسح للرسم البياني ، وغالبًا ما تستخدم في كل من الخوارزميات البسيطة والمتقدمة. يعمل بحث Breadth-First عن طريق التنقل خلال المستويات الفردية للرسم البياني ، بدءًا من العقدة المصدر والانتقال تدريجياً بعيدًا عنها. يظهر هذا بوضوح في الرسوم المتحركة.
لكتابة BFS بسيط ، يجب أن تكون قادرًا على العمل مع قائمة انتظار ، وهيكل بيانات يسمح لك بأخذها من البداية & nbsp ؛ ووضعها في النهاية ، وأيضًا أن تكون قادرًا على تخزين رسم بياني في النموذج من قائمة مجاورة.
نبسب ؛
وصف رسمي للخوارزمية
1) ضع رقم الرأس الذي يبدأ منه البحث في قائمة الانتظار الفارغة في البداية.
2) استخرج قمة الرأس U من بداية قائمة الانتظار وقم بتمييزها على أنها مستخدمة في مصفوفة منفصلة.
3) في نهاية قائمة الانتظار ، أضف جميع النقاط التي يمكننا الوصول إليها باستخدام الحافة من الرأس U والتي لم يتم تمييزها بعد.
4) إذا كانت قائمة الانتظار فارغة ، فهذا يعني أنه تم فحص جميع عقد الرسم البياني المتصل ، وإلا فارجع إلى الخطوة 2.
نبسب ؛
صعوبة العمل
نظرًا لأن الخوارزمية ، في أسوأ الحالات ، تزور جميع عقد الرسم البياني ، عند تخزين الرسم البياني في شكل قوائم مجاورة ، يكون التعقيد الزمني للخوارزمية هو O (| V | + | E |) ، حيث V هي المجموعة من رؤوس الرسم البياني ، و E هي مجموعة الحواف. & nbsp ؛ ؛
بمعنى آخر ، تعمل الخوارزمية في أسوأ الحالات بالنسبة لعدد الأضلاع + عدد الرؤوس.
نبسب ؛

Training problem

BFS: البداية (بايثون)

لاستعادة أقصر المسارات ، أنشئ مصفوفة من & quot؛ الأجداد & quot؛ & nbsp؛ \ (p [] \) ، حيث ، لكل رأس ، يتم تخزين رقم الرأس الذي نصل من خلاله إلى هذا الرأس.

Training problem

طريق