BFS مقابل DFS: الفرق والمقارنة

BFS و DFS كلاهما حيوي لنتائج الرسم البياني. يرمز BFS إلى بحث Breadth-First Search ، بينما يرمز DFS إلى Depth-First Search. كلاهما يميز بين الاثنين.

كلاهما يستخدم بنية بيانات مختلفة للأداء ، أحدهما يستخدم بنية بيانات قائمة الانتظار ، والآخر هو بنية البيانات المكدسة.

الوجبات السريعة الرئيسية

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

BFS مقابل DFS

يتمثل الاختلاف بين BFS و DFS في أن Breadth-First Search عبارة عن تقنية تعتمد على الرأس تساعد في الإشارة إلى أقصر مسار في الرسم البياني. من ناحية أخرى ، فإن DFS أو Depth First Search هي تقنية تعتمد على الحافة. BFS هي تقنية تعتمد على بنية بيانات قائمة الانتظار. من ناحية أخرى ، يعتمد DFS على بنية بيانات المكدس.

BFS هي تقنية يتم تطبيقها لمعرفة أقصر مسار في الرسم البياني باستخدام بنية بيانات قائمة الانتظار. إنه مناسب لإيجاد الرؤوس داخل مناطق قريبة من المصدر.

على عكس DFS ، لا يمكن تطبيقه بشكل أفضل في أشجار صنع القرار الموجودة في الألغاز أو الألعاب.

DFS هي تقنية يتم تطبيقها لاكتشاف أقصر مسار في الرسم البياني باستخدام بنية البيانات المكدسة. إنه مناسب للمناطق البعيدة عن المصادر داخل الحل.

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

جدول المقارنة

معلمات المقارنة	BFS	DFS
الشكل الكامل والتعريف	يرمز BFS إلى بحث Breadth-First. إنها تقنية تعتمد على الرأس وتُستخدم للعثور على أقصر طريق في الرسم البياني.	DFS هي اختصار لـ Depth First Search. إنها تقنية تعتمد على الحواف للعثور على أقصر طريق في الرسم البياني.
الاعتماد على بنية البيانات	يحدد Breadth-First Search أو BFS أقصر مسار في الرسم البياني بمساعدة بنية بيانات قائمة الانتظار.	يحدد Depth First Search أو DFS أقصر مسار في الرسم البياني بمساعدة بنية بيانات Stack.
استخدام	في الرسم البياني غير الموزون ، يتم استخدامه للعثور على أقصر مسار لمصدر واحد لأنه يستخدم أقل عدد من الحواف من مصدر الرأس.	في DFS ، للوصول إلى نقطة وجهة أو قمة من أي مصدر ، يجب اجتياز المزيد من الحواف.
مجال الملاءمة	مجال ملاءمتها لإيجاد نطاقات الرؤوس ضمن مدى قريب من المصدر. إنها غير مناسبة لصنع أشجار القرار الموجودة في الألعاب.	مجال ملاءمتها تتراوح ضمن حلول بعيدة عن المصدر. إنه أكثر ملاءمة لصنع القرار أو المشاكل في الألعاب أو الألغاز.
تقنية	في هذه التقنية ، يتم اختيار رأس واحد في وقت واحد أثناء زيارته ويتم تمييزه بعد ذلك يتم زيارة المنطقة المجاورة وتخزينها في قائمة الانتظار.	يتم وضع القمم التي تمت زيارتها في المكدس ثم في حالة عدم وجود الرؤوس ، يتم تفرقع القمم التي تمت زيارتها.

ما هو BFS؟

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

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

التعقيد الزمني لخوارزمية BFS هو O (V + E) خلال وقت القائمة المجاورة و O (V ^ 2) خلال وقت مصفوفة الجوار. هنا ، يرمز E إلى الحواف ، بينما يرمز V إلى الرؤوس.

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

يُستخدم BFS بشكل كبير في صياغة كل عقدة مجاورة في اتصالات نظير إلى نظير. تقوم برامج زحف محركات البحث ببناء الفهرس بمساعدة هذه التقنية.

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

يتم استخدام خوارزمية BFS أثناء بث بعض الحزم في الشبكات. تشمل خوارزمية تحديد المسار BFS.

بمساعدة هذه التقنية ، يمكن العثور على أعلى تدفق في الشبكة في خوارزمية Ford-Fulkerson.

ما هو DFS؟

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

يتم البحث أثناء حدوث أي تكرار. أثناء شجرة القرار ، يجب إجراء مزيد من التقاطع لزيادة القرار.

في الختام ، النصر معترف به. إنه سريع نسبيًا في السرعة من BFS. التعقيد الزمني لـ DFS هو O (V + E) أثناء القائمة المجاورة و O (V ^ 2) أثناء المصفوفة المجاورة.

هنا ، يرمز E إلى الحواف ، بينما يرمز V إلى الرؤوس. يستخدم DFS على نطاق واسع في مختلف المجالات.

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

إذا تم العثور على حافة خلفية واحدة في BFS، فهناك دورة واحدة. يمكن العثور على المسار بين u وv أو القممتين بمساعدة هذه التقنية.

تستخدم خوارزمية DFS للفرز الطوبولوجي. يمكن استخدامه لتحديد المكونات المرتبطة بقوة في رسم بياني معين.

تُصاغ المكونات لتكون متصلة بقوة عندما يكون هناك مسار بين كل قمة.

الاختلافات الرئيسية بين BFS و DFS

1. الشكل الكامل لـ BFS هو Breadth-First Search ، و DFS هو Depth First Search.
2. BFS هي تقنية تتمحور حول الرأس و DFS هي تقنية تتمحور حول الحافة.
3. يستخدم BFS بنية بيانات قائمة الانتظار ، لكن DFS يعمل مع بنية Stack Dara.
4. يعمل BFS على تحديد أقصر مسار لمصدر واحد نظرًا لأنه يستخدم الحد الأدنى لعدد الحواف من أصل الرأس. من ناحية أخرى ، يستخدم DFS المزيد من الحواف للعبور للوصول إلى نقطة الوجهة أو الرأس.
5. BFS غير مناسب للتطبيق في أشجار صنع القرار الموجودة في الألغاز أو الألعاب. من ناحية أخرى ، تعد DFS مناسبة لحل المشكلات في الألعاب.

مراجع حسابات

1. https://link.springer.com/chapter/10.1007/978-3-319-26350-2_14
2. https://link.springer.com/chapter/10.1007/978-3-319-42634-1_10