BFS و DFS هي طرق عبور المستخدمة في البحث في الرسم البياني. اجتياز الرسم البياني هو عملية زيارة جميع العقد في الرسم البياني. الرسم البياني هو مجموعة من Vertices 'V' و Edges 'E' ترتبط بالرؤوس.
رسم بياني للمقارنة
| أساس للمقارنة | BFS | DFS |
|---|---|---|
| الأساسية | خوارزمية تستند إلى قمة الرأس | خوارزمية قائمة على الحواف |
| هيكل البيانات المستخدم لتخزين العقد | طابور | كومة |
| استهلاك الذاكرة | غير فعال | فعالة |
| هيكل الشجرة المبنية | واسعة وقصيرة | ضيق وطويل |
| عبور الموضة | يتم استكشاف القمم الأولى غير المنظورة في البداية. | يتم استكشاف القمم على طول الحافة في البداية. |
| الأمثلية | الأمثل للعثور على أقصر مسافة ، وليس في التكلفة. | ليس الأمثل |
| الوضعية | يفحص الرسم البياني ثنائي الاتجاه ، والمكون المتصل وأقصر مسار موجود في الرسم البياني. | يدرس الرسم البياني المتصل الحافة ، والرسم البياني الموصل بقوة ، والرسم البياني غير الدائري ، والترتيب الطوبولوجي. |
تعريف BFS
اتساع البحث الأول (BFS) هو طريقة عبور المستخدمة في الرسوم البيانية. ويستخدم قائمة انتظار لتخزين الرؤوس التي تمت زيارتها. في هذه الطريقة يتم التركيز على رؤوس الرسم البياني ، يتم تحديد قمة الرأس في البداية ثم يتم زيارتها وتمييزها. ثم يتم زيارة القمم المجاورة للقمة زار وتخزينها في قائمة الانتظار بالتسلسل. وبالمثل ، يتم التعامل مع الرؤوس المخزنة واحدة تلو الأخرى ، ويتم زيارة القمم المجاورة لها. يتم استكشاف عقدة بشكل كامل قبل زيارة أي عقدة أخرى في الرسم البياني ، وبعبارة أخرى ، فإنه يجتاز العقد الضحلة غير مستكشفة أولاً.
مثال
لدينا رسم بياني له القمم A ، B ، C ، D ، E ، F ، G. اعتبار A كنقطة بداية. الخطوات المتبعة في العملية هي:
- يتم توسيع Vertex A وتخزينها في قائمة الانتظار.
- يتم توسيع وتخزين الرؤوس B و D و G من A ، وتخزينها في قائمة الانتظار وفي الوقت نفسه Vertex A إزالتها.
- تتم الآن إزالة B في الواجهة الأمامية من قائمة الانتظار مع تخزين القمم اللاحقة E و F.
- تتم إزالة Vertex D في الجزء الأمامي من قائمة الانتظار تتم إزالتها ، وقد تمت زيارة العقدة المتصلة بها F بالفعل.
- تتم إزالة Vertex G من قائمة الانتظار ، ولديه خليفة E الذي تمت زيارته بالفعل.
- الآن تتم إزالة E و F من قائمة الانتظار ، ويتم اجتياز الجزء الخلف لـ C الخاص به وتخزينه في قائمة الانتظار.
- في الماضي C أيضا إزالة وقائمة الانتظار فارغة مما يعني أننا الانتهاء من ذلك.
- الناتج الناتج هو - A ، B ، D ، G ، E ، F ، C.
يمكن أن يكون BFS مفيدًا في تحديد ما إذا كان الرسم البياني قد قام بتوصيل المكونات أم لا. وأيضا يمكن استخدامه في الكشف عن رسم بياني ثنائي .
الرسم البياني هو ثنائي البارامترات عندما تنقسم الرؤوس البيانية إلى مجموعتين منفصلتين ؛ لا يوجد أي رأسين متجاورين في نفس المجموعة. هناك طريقة أخرى لفحص الرسم البياني ثنائي الدرجة هي التحقق من حدوث دورة فردية في الرسم البياني. يجب ألا يحتوي الرسم البياني ثنائي الاتجاه على دورة فردية.
BFS هو أيضا أفضل في العثور على أقصر مسار في الرسم البياني يمكن أن ينظر إليه على أنه شبكة.
تعريف DFS
يستخدم أسلوب عبور البحث الأول (DFS) رصة التخزين لتخزين الرؤوس التي تمت زيارتها. DFS هو الأسلوب القائم على الحافة ويعمل بطريقة متكررة حيث يتم استكشاف القمم على طول المسار (الحافة). يتم تعليق استكشاف العقدة بمجرد العثور على عقدة أخرى غير مستكشفة ويتم اجتياز العقد غير المستكشفة الأعمق في المقام الأول. DFS اجتياز / زيارة كل قمة مرة واحدة بالضبط ويتم فحص كل حافة بالضبط مرتين.
مثال
مماثلة ل BFS يتيح أخذ نفس الرسم البياني لتنفيذ عمليات DFS ، والخطوات المعنية هي:
- النظر في A باعتباره قمة الرأس التي يتم استكشافها وتخزينها في المكدس.
- يتم تخزين B الخلف اللاحق لـ A في الرصة.
- يحتوي Vertex B على خليتين متعاقبتين E و F ، من بينها الأبجدية E يتم استكشافها أولاً وتخزينها في المكدس.
- يتم تخزين خليفة الرأس E ، أي ، G في الرصة.
- يوجد في الرأس Vertex G رأسيين متصلين ، وتمت زيارة كل منهما بالفعل ، ومن ثم خرج G من الحزمة.
- وبالمثل ، تم إزالة E s أيضًا.
- الآن ، قمة الرأس B في الجزء العلوي من المكدس ، يتم استكشاف عقدة أخرى (قمة الرأس) F وتخزينها في المكدس.
- يحتوي Vertex F على خليتين C و D ، بينهما يتم عبور C أولاً وتخزينهما في الكدسة.
- لدى Vertex C سلفًا واحد فقط تمت زيارته بالفعل ، لذا تتم إزالته من الرصة.
- يتم الآن زيارة قمة الرأس D المرتبطة بـ F وتخزينها في المكدس.
- نظرًا لأن قمة الرأس لا تحتوي على أي عقد غير متوقع ، فيتم إزالة D.
- وبالمثل ، فإن F و B و A تظهر أيضًا.
- الناتج الذي تم إنشاؤه هو - A ، B ، E ، G ، F ، C ، D.
تتضمن تطبيقات DFS فحص رسم بياني متجرد متصل ، رسم بياني متصل بقوة ، رسم بياني حلقي ، وترتيب توبولوجي .
يُسمى الرسم البياني حافتين متصلين إذا وفقطت تظل متصلة حتى إذا تمت إزالة أحد حوافها. هذا التطبيق مفيد جدا ، في شبكات الكمبيوتر حيث لن يؤثر فشل وصلة واحدة في الشبكة على الشبكة المتبقية ، وسيكون لا يزال متصلا.
الرسم البياني المرتبط بقوة هو رسم بياني يجب أن يوجد فيه مسار بين زوج من القمم المطلوبة. يتم استخدام DFS في الرسم البياني الموجه للبحث في المسار بين كل زوج من القمم المطلوبة. يمكن DFS حل مشاكل الاتصال بسهولة.
الاختلافات الأساسية بين BFS و DFS
- BFS هو خوارزمية يستند إلى قمة الرأس بينما DFS خوارزمية تستند إلى حافة.
- يتم استخدام بنية بيانات قائمة الانتظار في BFS. من ناحية أخرى ، يستخدم DFS مكدس أو العودية.
- يتم استخدام مساحة الذاكرة بكفاءة في DFS بينما لا يكون استخدام المساحة في BFS فعالاً.
- BFS هو خوارزمية الأمثل بينما DFS غير الأمثل.
- DFS يبني أشجار ضيقة وطويلة. مقابل ذلك ، ينشئ BFS شجرة واسعة وقصيرة.
استنتاج
BFS و DFS ، كلاهما من تقنيات البحث عن الرسم البياني لهما وقت تشغيل متشابهان ولكنهما مختلفان في استهلاك الفضاء ، DFS يأخذ مساحة خطية لأننا يجب أن نتذكر مسار واحد مع عقد غير مستكشفة ، بينما BFS تحتفظ بكل عقدة في الذاكرة.
تنتج DFS حلول أعمق وليست مثالية ، ولكنها تعمل بشكل جيد عندما يكون الحل كثيفًا بينما BFS هو الأمثل الذي يبحث عن الهدف الأمثل في البداية.
