العمق الأول مقابل عرض البحث الأول

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

ما هي الشجرة؟

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

دعنا ننهار المخطط.

تحتوي كل شجرة على عقدة جذر واحدة في المستوى الأعلى (في هذه الحالة ، المستوى 0). ثم نرى أنه في المستوى التالي ، تحتوي عقدة الجذر A على مؤشرات إلى العقدتين B و C. وبالمثل ، فإن العقدتين B و C تحتويان على مؤشرات إلى العقدة A. أطفالها. علاوة على ذلك ، تعتبر العقدتان B و C أشقاء.

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

كود الشجرة

إخلاء مسؤولية: سأستخدم Javascript لإنشاء شجرة بسيطة!

أولاً ، نحتاج إلى إنشاء فئة عقدة:

عندما ننشئ فئة العقدة ، فإننا نمررها قيمة ، أو بيانات ، والتي تصبح خاصية بيانات العقدة. لدينا أيضًا خصائص الوالدين والطفل والتي تعد صفيفًا وفارغًا ، على التوالي ، في الوقت الحالي. في النهاية ، ستشير الخاصية الأصل إلى أصل العقدة المحددة وستشير الخاصية التابعة إلى أطفال العقدة.

ثم ، نخلق فئة شجرة:

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

البحث!

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

نهج العمق الأول

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

ترتيب البحث: [10 ، 4 ، 1 ، 9 ، 17 ، 12 ، 18]

الشفرة

البحث في العمق الأول يأخذ قيمة كحجة وهي القيمة التي نبحث عنها في الشجرة. نظرًا لأننا نريد اجتياز العقد من اليسار إلى اليمين ، فقد قمنا بتعيين الجذر كدقة لأننا نريد أن نأخذ النهج الأول في الخروج أولاً. ثم نقوم بإجراء حلقة من الوقت تستمر طالما أن الرصة تحتوي على عناصر. ضمن حلقة أثناء ، نقوم بإزالة العنصر الأول في المكدس ، أو استدعاء طريقة الصفيف shift () ، وتعيينه يساوي عقدة. نحن نقارن بيانات هذه العقدة بقيمة الوسيطة ، وإذا كانت متطابقة ، فتُرجع الدالة true. إذا لم يكن الأمر كذلك ، فإنها تضيف أطفال العقدة إلى مقدمة المكدس ، أو تستدعي طريقة الصفيف unshift () ، وتستمر في البحث من خلال البيانات الجديدة. إذا كانت القيمة الخاصة غير موجودة في الشجرة ، فسوف تُرجع الدالة false.

منهج العرض الأول

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

ترتيب البحث: [10 ، 4 ، 17 ، 1 ، 9 ، 12 ، 18]

الشفرة

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

أيها أستخدم؟

على الرغم من أن عمليات البحث في العمق الأول (DFS) والبحث الأول (BFS) تعد نهجين مشروعين ويمكنهما الوصول إلى نفس الاستنتاجات ، إلا أن كل واحدة يتم تفضيلها في ظل ظروف معينة. ومع ذلك ، فليس من الواضح غالبًا أيهما أكثر فاعلية من الاثنين.

إخلاء المسئولية: هذه إرشادات عامة! بالتأكيد ليست دائما أفضل الطرق.

DFS: يفضل بشكل عام عندما تكون الشجرة عميقة جدًا وتحدث القيم أو البيانات المطلوبة بشكل غير منتظم.

BFS: يفضل عمومًا في الأشجار الضحلة التي ليست واسعة جدًا. يستخدم أيضًا إذا كان معروفًا أن العقدة المطلوبة أقرب إلى مستوى الجذر.

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

على سبيل المثال ، دعنا نفترض أنك تستخدم الشجرة أعلاه وتبحث عن العقدة التي تحتوي على 8. الشجرة ليست عميقة جدًا لذا قد تعتقد أنه من الأفضل استخدام BFS. ومع ذلك ، سيكون في الواقع أكثر كفاءة لاستخدام DFS.

دعنا نقارن بين الطريقتين والعقد التي تم اجتيازها:

DFS: 1 ، 2 ، 4 ، 8

BFS: 1 ، 2 ، 3 ، 4 ، 5 ، 6 ، 7 ، 8

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

علاوة على ذلك ، بمجرد تحديد موقع العقدة 8 ، ستكون رصة DFS [8 ، 9 ، 5 ، 3] بينما ستكون قائمة انتظار BFS [8 ، 9 ، 10 ، 11 ، 13 ، 14]. تحتوي قائمة انتظار BFS على عقدتين أخريين ، والتي لا يبدو أنها تساوي الكثير في هذا المثال ، لكن فيما يتعلق بالذاكرة ، لا تزال تستخدم مقدارًا أكبر. لذلك ، في هذه الحالة بالذات ، سيكون DFS أكثر كفاءة من BFS.

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

تعقيد

تعقيد الزمان والمكان لكلا DFS و BFS واضحان للغاية. نظرًا لأننا نتحدث عن اجتياز شجرة ، من أجل تحديد ما إذا كانت هناك قيمة أو بيانات موجودة داخل الشجرة ، يجب علينا زيارة كل عقدة. زيارة كل عقدة في وقت واحد تعني أن تعقيد الوقت لكل من DFS و BFS هما O (n) أو خطي. إذا فكرنا في الأشجار على أنها صفائف مفروزة ، فسنضطر إلى التكرار خلال وقت واحد لتحديد ما إذا كانت القيمة تتطابق مع القيمة التي نبحث عنها أم لا. وبالمثل ، من حيث تعقيد الفضاء ، DFS هي O (h) و BFS هي O (w). بالنسبة لـ DFS ، stands h تعني الارتفاع نظرًا لأن مقدار المساحة التي ستتخذها الوظيفة يعتمد على عدد العقد الموجودة في الشجرة. وبالمثل ، بالنسبة لـ BFS ، 'w' تعني العرض ، لأن المساحة تعتمد على مدى عرض الشجرة. بالطبع ، تتغير هذه الرموز الكبيرة O بناءً على بنية البيانات ، ولكن من أجل الأشجار ، ستكون التعقيدات الزمنية والفضائية هي نفسها.

شكرا لأخذ الوقت الكافي لقراءة هذا المقال! إذا كان لديك أي ملاحظات أو أسئلة ، اسمحوا لي أن أعرف! أتمنى لك يوم رائع!