BFS مقابل DFS للشجرة الثنائية


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون انفوسيس MAQ TCS
اتساع البحث الأول عمق البحث الأول نظرية شجرة

اتساع البحث الأول (BFS)

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

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

عمق البحث الأول (DFS)

هل ندرك أيضًا ما هو DFS في الواقع؟ يمكنك زيارة مقالتنا السابقة على عمق البحث الأول. DFS لـ BT عبارة عن ثلاثة أنواع من الاجتياز:

  1. اجتياز الطلب المسبق
  2. اجتياز الداخل
  3. اجتياز الطلب البريدي

اجتياز الطلب المسبق

Algorithm:
Preorder(root):
Step:1 Print the data of the Node.
Step:2 Move to the left side of the node(traverse left-subtree).
Step:3 Move to the right side of the node(traverse right-subtree).

اجتياز الداخل

Algorithm: 
Inorder(root): 
Step:1 Move to the left side of the node(traverse left-subtree).
Step:2 Print the data of the Node.  
Step:3 Move to the right side of the node(traverse right-subtree).

اجتياز الطلب البريدي

Algorithm: 
Postorder(root):  
Step:1 Move to the left side of the node(traverse left-subtree). 
Step:2 Move to the right side of the node(traverse right-subtree).
Step:3 Print the data of the Node.

Difference بين BFS و DFS لشجرة ثنائية

نوع بنية البيانات المستخدمة

في BFS نستخدم ملف طابور اكتب بنية البيانات وفي DFS نستخدم ملف كومة اكتب بنية البيانات.

تعقيد الفضاء

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

تعقيد الوقت

الوقت سيكون تعقيد كلتا الحالتين هو O (N + E) حيث تشير N إلى العقد الإجمالية في BT و E تشير إلى الحواف الإجمالية في BT.

البحث عن عقدة أقرب إلى عقدة الجذر

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

البحث عن عقدة بعيدة عن عقدة الجذر

للحصول على أفضل نتيجة ، نستخدم DFS في هذه الحالة لأنه يتبع مفهوم العمق.

معنى

BFS تعني بحث Breadth-first و DFS بمعنى بحث العمق أولاً.

نوع بنية البيانات المستخدمة

استخدم BFS بنية بيانات نوع قائمة الانتظار واستخدم DFS بنية بيانات نوع Stack.

أساسي

BFS هي خوارزمية قائمة على قمة الرأس و DFS هي خوارزمية قائمة على الحافة.

سرعة

BFS أبطأ من DFS.

الرقم المرجعي

اسئلة المقابلة