ما هو بفس؟

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

خوارزمية بفس

فيما يلي الخطوات المتبعة في استخدام بحث الاتساع أولاً لاستكشاف الرسم البياني:

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

تطبيقات بفس

نظرًا لمرونة الخوارزمية، يعد البحث الموسع أولًا مفيدًا جدًا في العالم الحقيقي. هذه هي بعض منها:

1. في شبكة نظير إلى نظير، يتم اكتشاف عقد النظير. يستخدم معظم عملاء التورنت، مثل BitTorrent وuTorrent وqBittorent، هذه العملية للعثور على 'البذور' و'الأقران' في الشبكة.
2. تم إنشاء الفهرس باستخدام تقنيات اجتياز الرسم البياني في الزحف على الويب. يبدأ الإجراء بالصفحة المصدر باعتبارها العقدة الجذرية ويصل إلى جميع الصفحات الثانوية المرتبطة بالصفحة المصدر (وتستمر هذه العملية). نظرًا للعمق المنخفض لشجرة العودية، يتمتع البحث بالعرض الأول بميزة متأصلة هنا.
3. استخدام أنظمة الملاحة GPS باستخدام نظام تحديد المواقع العالمي (GPS)، قم بإجراء بحث واسع النطاق لتحديد المواقع القريبة.
4. يتم استخدام أسلوب تشيني، الذي يستخدم مفهوم البحث الموسع أولاً، لجمع القمامة.

مثال اجتياز BFS

للبدء، دعونا نلقي نظرة على مثال بسيط. سنبدأ بالرقم 0 كعقدة الجذر ونعمل في طريقنا إلى أسفل الرسم البياني.

الخطوة 1: سرد(0)

طابور

الخطوة 2: Dequeue(0)، Enqueue(1)، Enqueue(3)، Enqueue(4)

طابور

الخطوه 3: طابور (1)، طابور (2)

طابور

الخطوة 4: طابور(3)، طابور(5). لن نضيف 1 إلى قائمة الانتظار مرة أخرى لأنه تم استكشاف 0 بالفعل.

طابور

الخطوة 5: قائمة الانتظار(4)

طابور

الخطوة 6: قائمة الانتظار(2)

طابور

الخطوة 7: قائمة الانتظار(5)

طابور

قائمة الانتظار فارغة الآن لذا سنوقف العملية.

برنامج جافا للبحث ذو العرض الأول

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

سيكون الرسم البياني المستخدم لتوضيح الكود مطابقًا للرسم البياني المستخدم في المثال السابق.

BFStraversal.java

 import java.io.*; import java.util.*; public class BFSTraversal { private int node; /* total number number of nodes in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { node = v; adj = new LinkedList[node]; for (int i=0; i<v; i++) { adj[i]="new" linkedlist(); } que="new" void insertedge(int v,int w) adj[v].add(w); * adding an edge to the adjacency list (edges are bidirectional in this example) bfs(int n) boolean nodes[]="new" boolean[node]; initialize array for holding data int a="0;" nodes[n]="true;" que.add(n); root node is added top of queue while (que.size() !="0)" n="que.poll();" remove element system.out.print(n+' '); print (int i="0;" < adj[n].size(); iterate through linked and push all neighbors into if (!nodes[a]) only insert nodes they have not been explored already nodes[a]="true;" que.add(a); public static main(string args[]) bfstraversal graph="new" bfstraversal(6); graph.insertedge(0, 1); 3); 4); graph.insertedge(4, 5); graph.insertedge(3, graph.insertedge(1, 2); 0); graph.insertedge(2, graph.insertedge(5, system.out.println('breadth first traversal is:'); graph.bfs(0); pre> <p> <strong>Output:</strong> </p> <pre> Breadth First Traversal for the graph is: 0 1 3 4 2 5 </pre> <hr></v;>