بحث النطاق الأول - دليل اجتياز الرسم البياني BFS مع 3 أمثلة لـ Leetcode

يعد Breadth First Search (BFS) أحد أكثر الخوارزميات شيوعًا للبحث أو عبور شجرة أو بنية بيانات الرسم البياني. في هذا البرنامج التعليمي ، سوف نتعلم بإيجاز كيفية عمل BFS واستكشاف النمط الأساسي الذي يمكن استخدامه لحل بعض المشكلات المتوسطة والسهلة في Leetcode.

دعنا نبدأ ، نحن العرب؟

ما هو اتساع البحث الأول؟

لذلك ، نعلم جميعًا أن الرسم البياني عبارة عن مجموعة من الرؤوس والحواف: G = {V، E}. يعني اجتياز الرسم البياني زيارة كل رأس وكل حافة مرة واحدة بالضبط بطريقة منظمة.

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

لذلك ، عندما يُطلب منا إجراء بعض اجتياز ترتيب المستوى ، يمكننا استخدام تقنية BFS.

في BFS ، نبدأ بالانتقال من 1 (العقدة الجذرية) وزيارة العقد الفرعية 8 و 5 و 2. سنقوم بتخزينها بالترتيب الذي تمت زيارتها. سيسمح لنا هذا بزيارة العقد الفرعية المكونة من 8 أولًا (أي 6 و 4 و 3) ، ثم من 5 (أي فارغة) ، ثم 2 (أي 9) وهكذا.

التنفيذ

من أجل تنفيذ BFS ، يتم استخدام بنية بيانات قائمة الانتظار . تقوم قائمة الانتظار بتخزين العقدة وتمييزها على أنها "تمت زيارتها" حتى يتم تمييز جميع الرؤوس المجاورة لها.

قائمة الانتظار تتبع طريقة First In First Out (FIFO). هذا يعني أنه سيتم زيارة جيران العقدة بالترتيب الذي تم إدخالهم به.

تعويذة BFS السحرية:

  1. أضف عقدة إلى قائمة الانتظار
  2. قم بإزالة العقدة
  3. استرجع الجيران الذين لم تتم زيارتها للعقدة التي تمت إزالتها ، وأضفهم إلى قائمة الانتظار
  4. كرر الخطوات 1 و 2 و 3 طالما أن قائمة الانتظار ليست فارغة.

الآن دعنا نلقي نظرة على بعض مشاكل Leetcode ونطبق ما تعلمناه.

102. اجتياز ترتيب مستوى الشجرة الثنائية (الصعوبة: متوسطة)

يطلب منا السؤال اجتياز الرسم البياني وطباعة العقد في كل مستوى في قائمة مرتبطة. لحل هذه المشكلة ، كل ما علينا فعله هو تطبيق تعويذتنا السحرية!

تأكد من أنك تفهم الكود جيدًا ، لأن هذا هو النموذج الأساسي الذي سنستخدمه لحل مشكلات متعددة. لذلك دعونا نمر بها.

في الكود أعلاه ، أدخلنا في البداية عقدة الجذر في قائمة الانتظار. في حين أن قائمة الانتظار ليست فارغة ، فقد أزلنا هذه العقدة من قائمة الانتظار وأدخلنا الطفل الأيسر والأيمن في قائمة الانتظار.

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

تتكرر العملية مرة أخرى مع العناصر التالية التي تظل في قائمة الانتظار. و للحلقةيتم الاحتفاظ بها لتزويدنا بقائمة بالعقد في كل مستوى في قوائم مرتبطة منفصلة.

637. متوسط ​​المستويات في شجرة ثنائية (الصعوبة: سهل)

يخبرنا هذا السؤال بإيجاد متوسط ​​قيمة العقد في كل مستوى من مستويات الشجرة الثنائية في المصفوفة. هذا يتبع نفس الإجراء مثل مشكلتنا السابقة مع القليل من القرص.

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

429. اجتياز ترتيب مستوى شجرة N-ary (الصعوبة: متوسطة)

تسمى الشجرة التي لا تحتوي كل عقدة فيها على أكثر من N عدد من الأطفال بشجرة N-ary.

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

هذا كل شئ! آمل أن يكون هذا قد ساعدك على فهم BFS بشكل أفضل وأنك استمتعت بالبرنامج التعليمي. يرجى التوصية بهذا المنشور إذا كنت تعتقد أنه قد يكون مفيدًا لشخص آخر!