خوارزمية بفس

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

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

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

يتم إعطاء تطبيقات خوارزمية العرض الأول على النحو التالي -

ولد فريدي ميركوري

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

خوارزمية

يتم إعطاء الخطوات المتبعة في خوارزمية BFS لاستكشاف الرسم البياني على النحو التالي -

الخطوة 1: SET STATUS = 1 (حالة الاستعداد) لكل عقدة في G

الخطوة 2: ضع عقدة البداية A في قائمة الانتظار وقم بتعيين حالتها = 2 (حالة الانتظار)

الخطوه 3: كرر الخطوتين 4 و5 حتى تصبح قائمة الانتظار فارغة

الخطوة 4: قم بإزالة عقدة N. قم بمعالجتها وتعيين حالتها = 3 (حالة المعالجة).

الخطوة 5: قم بوضع جميع جيران N الموجودين في حالة الاستعداد (التي حالتها = 1) في قائمة الانتظار ثم قم بتعيينها

حالتهم = 2

(حالة الانتظار)

[نهاية الحلقة]

الخطوة 6: مخرج

مثال على خوارزمية BFS

الآن، دعونا نفهم عمل خوارزمية BFS باستخدام مثال. في المثال الموضح أدناه، يوجد رسم بياني موجه له 7 رؤوس.

قائمة المصفوفات والقائمة المرتبطة

في الرسم البياني أعلاه، يمكن العثور على الحد الأدنى للمسار 'P' باستخدام BFS الذي سيبدأ من العقدة A وينتهي عند العقدة E. تستخدم الخوارزمية قائمتي انتظار، وهما QUEUE1 وQUEUE2. يحتفظ QUEUE1 بجميع العقد التي سيتم معالجتها، بينما يحتفظ QUEUE2 بجميع العقد التي تتم معالجتها وحذفها من QUEUE1.

الآن، لنبدأ بفحص الرسم البياني بدءًا من العقدة A.

الخطوة 1 - أولاً، أضف A إلى قائمة الانتظار 1 وNULL إلى قائمة الانتظار 2.

ما هو حجم هذه الشاشة

 QUEUE1 = {A} QUEUE2 = {NULL}

الخطوة 2 - الآن، احذف العقدة A من قائمة الانتظار 1 وأضفها إلى قائمة الانتظار 2. أدخل جميع جيران العقدة A في قائمة الانتظار 1.

 QUEUE1 = {B, D} QUEUE2 = {A}

الخطوه 3 - الآن، احذف العقدة B من قائمة الانتظار 1 وأضفها إلى قائمة الانتظار 2. أدخل جميع جيران العقدة B في قائمة الانتظار 1.

 QUEUE1 = {D, C, F} QUEUE2 = {A, B}

الخطوة 4 - الآن، احذف العقدة D من قائمة الانتظار 1 وأضفها إلى قائمة الانتظار 2. أدخل جميع جيران العقدة D في قائمة الانتظار 1. الجار الوحيد للعقدة D هو F لأنه تم إدراجه بالفعل، لذلك لن يتم إدراجه مرة أخرى.

 QUEUE1 = {C, F} QUEUE2 = {A, B, D}

الخطوة 5 - احذف العقدة C من قائمة الانتظار 1 وأضفها إلى قائمة الانتظار 2. أدخل جميع جيران العقدة C في قائمة الانتظار 1.

 QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C}

الخطوة 5 - احذف العقدة F من قائمة الانتظار 1 وأضفها إلى قائمة الانتظار 2. أدخل جميع جيران العقدة F في قائمة الانتظار 1. نظرًا لأن جميع جيران العقدة F موجودون بالفعل، فلن نقوم بإدراجهم مرة أخرى.

 QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F}

الخطوة 6 - حذف العقدة E من قائمة الانتظار 1. نظرًا لأنه تمت إضافة جميع جيرانه بالفعل، فلن نقوم بإدراجهم مرة أخرى. الآن، تمت زيارة جميع العقد، وتم العثور على العقدة المستهدفة E في قائمة الانتظار 2.

 QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E}

تعقيد خوارزمية BFS

يعتمد التعقيد الزمني لـ BFS على بنية البيانات المستخدمة لتمثيل الرسم البياني. التعقيد الزمني لخوارزمية BFS هو يا (الخامس + ه) لأنه في أسوأ الحالات، تستكشف خوارزمية BFS كل عقدة وحافة. في الرسم البياني، عدد القمم هو O(V)، في حين أن عدد الحواف هو O(E).

يمكن التعبير عن التعقيد المكاني لـ BFS كـ يا (الخامس) ، حيث V هو عدد القمم.

قائمة فرز المصفوفة

تنفيذ خوارزمية BFS

الآن، دعونا نرى تنفيذ خوارزمية BFS في جافا.

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

في هذا المثال، الرسم البياني الذي نستخدمه لتوضيح الكود هو كما يلي -

 import java.io.*; import java.util.*; public class BFSTraversal { private int vertex; /* total number number of vertices in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { vertex = v; adj = new LinkedList[vertex]; 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[vertex]; 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(10); graph.insertedge(0, 1); 2); 3); graph.insertedge(1, graph.insertedge(2, 4); graph.insertedge(3, 5); 6); graph.insertedge(4, 7); graph.insertedge(5, graph.insertedge(6, graph.insertedge(7, 8); system.out.println('breadth first traversal is:'); graph.bfs(2); pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/64/bfs-algorithm-3.webp" alt="Breadth First Search Algorithm"> <h3>Conclusion</h3> <p>In this article, we have discussed the Breadth-first search technique along with its example, complexity, and implementation in java programming language. Here, we have also seen the real-life applications of BFS that show it the important data structure algorithm.</p> <p>So, that&apos;s all about the article. Hope, it will be helpful and informative to you.</p> <hr></v;>