توسيع خوارزمية البحث الأول: نظرة عامة ، الأهمية والتطبيقات

الرسوم البيانية في كل مكان حولنا. يمكن اعتبار الرسم البياني بمثابة شبكة مترابطة من العقد والحواف. يشكل أصدقاؤك على Facebook أو اتصالاتك على LinkedIn أو متابعو Twitter / Instagram الرسم البياني الاجتماعي الخاص بك. وبالمثل ، إذا كنت تريد الانتقال من النقطة "أ" إلى النقطة "ب" ، فيمكنك القيام بذلك عبر طرق متعددة ، والتي يمكن تصورها على خرائط Google.

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

ما هو رسم الرسم البياني؟

Graph Traversal هي طريقة لزيارة كل عقدة في الرسم البياني مرة واحدة بالضبط بسرعة ودقة. إنها خوارزمية بحث عن الرسم البياني المتقدمة تمكنك من طباعة تسلسل العقد التي تمت زيارتها دون الوقوع في حلقة لا نهائية. هناك العديد من خوارزميات اجتياز الرسم البياني مثل Depth-First Search و Breadth -First Search وخوارزمية Djikstra وخوارزمية A-Star والمزيد.

ستأخذ هذه المقالة نظرة عميقة في خوارزمية Breadth First Search أو BFS.

هيكل الرسم البياني

قبل أن نلقي نظرة مفصلة على غطاء محرك BFS ، دعونا نتعرف على بعض مصطلحات الرسم البياني بمساعدة الرسم البياني أعلاه:

عقدة الجذر - العقدة التي تبدأ فيها عملية الاجتياز. للتبسيط ، يمكننا اعتبار أن A هي العقدة الجذرية.

المستويات - المستوى عبارة عن مجموعة من جميع العقد التي تكون على مسافات متساوية من عقدة الجذر. لذلك ، إذا اعتبرنا أن العقدة A في المستوى 0 ، فإن العقدتين B و C في المستوى 1 ، بينما العقد D و E و F في المستوى 2. ومن الإرشادات البسيطة لتحديد رقم مستوى العقدة حساب الرقم من الحواف بين العقدة المذكورة وعقدة الجذر. لاحظ أن هذا لا يعمل إلا إذا قمت بتعريف العقدة الجذرية لتكون في المستوى 0.

العقدة الأصلية - العقدة الأصلية للعقدة هي تلك الموجودة فوق مستوى واحد والمجاورة لها. يمكن اعتبارها بمثابة العقدة التي تنشأ منها العقدة المذكورة. A هي العقدة الأصلية لـ B و C.

العقد الفرعية / الفرعية - العقدة (العقد) التي تتفرع والمجاورة للعقدة الأصلية. B و C عقدتان فرعيتان لـ A

قراءة: أفضل 10 تقنيات لتصور البيانات

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

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

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

() - يدل على قائمة الانتظار

[] - يدل على الإخراج المطبوع

1. أدخل A في قائمة الانتظار (أ)
2. اطبع A ، أدخل B و C في قائمة الانتظار (cb) [a]
3. اطبع B ، أدخل العقدتين الفرعيتين D و E في قائمة الانتظار (EDC) [ba]
4. اطبع C ، أدخل العقدة الفرعية F الخاصة بها في قائمة الانتظار (التغذية) [cba]
5. اطبع D ، أدخل العقدة التابعة لها في قائمة الانتظار. لا يوجد. (fe) [dcba]
6. Print E ، الذي تم بالفعل إدراج العقدة الفرعية F الخاصة به في قائمة الانتظار. (و) [إدكبا]
7. طباعة F. [fedcba]

ما الذي يجعل خوارزمية BFS مهمة

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

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

الخروج: مشاريع تصور البيانات التي يمكنك تكرارها

تطبيقات خوارزمية BFS

نظرًا لبساطتها وسهولة إعدادها ، وجدت خوارزمية BFS استخدامًا واسع النطاق في العديد من المواقف الرئيسية في العالم الحقيقي. دعونا نلقي نظرة على بعض التطبيقات البارزة:

برامج زحف محرك البحث - حاول تخيل عالم بدون Google أو Bing. لا يمكنك. محركات البحث هي العمود الفقري للإنترنت. وخوارزمية BFS هي العمود الفقري لمحركات البحث. إنها الخوارزمية الأساسية المستخدمة لفهرسة صفحات الويب. تبدأ الخوارزمية رحلتها من الصفحة المصدر (عقدة الجذر) ثم تتبع جميع الروابط الموجودة على صفحة المصدر هذه بطريقة واسعة النطاق. يمكن اعتبار كل صفحة ويب كعقدة مستقلة في الرسم البياني.

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

نظام تحديد المواقع العالمي (GPS ) - يستفيد BFS من أنظمة GPS لإبراز جميع المواقع المجاورة المحتملة من نقطة البداية ، مما يساعدك على التنقل من النقطة A إلى B بسلاسة.

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

شبكات P2P - تعتمد السيول أو شبكات مشاركة الملفات الأخرى على اتصال P2P. يعمل BFS بشكل ممتاز للعثور على أقرب العقد بحيث يمكن نقل البيانات بشكل أسرع.

اقرأ أيضًا: فوائد تصور البيانات

خاتمة

Ergo ، خوارزمية Breadth First Search هي واحدة من أهم خوارزميات الإنترنت الحديثة. نأمل أن تكون هذه المدونة بمثابة نقطة انطلاق مفيدة في استكشافات خوارزمية البحث.

نوصيك باختيار دبلوم PG في علوم البيانات الذي يقدمه معهد IIIT Bangalore المستضاف على upGrad لأنه يمكنك هنا الحصول على استفساراتك 1-1 مع مدربي الدورة. لا يركز فقط على التعلم النظري ولكنه يعطي أهمية للمعرفة العملية ، وهو أمر ضروري لإعداد المتعلمين لمواجهة مشاريع العالم الحقيقي وتزويدك بشهادة NASSCOM الأولى في الهند ، والتي تساعدك في الحصول على وظائف عالية الأجر في علوم البيانات.