TechCodeview

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

بسبب الطبيعة العودية، يمكن استخدام بنية بيانات المكدس لتنفيذ خوارزمية DFS. تشبه عملية تنفيذ DFS خوارزمية BFS.

يتم تقديم العملية خطوة بخطوة لتنفيذ اجتياز DFS على النحو التالي -

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

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

وترد تطبيقات استخدام خوارزمية DFS على النحو التالي -

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

خوارزمية

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

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

دمج الفرز في جافا

الخطوه 3: كرر الخطوتين 4 و5 حتى يصبح STACK فارغًا

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

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

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

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

كود مزيف

 DFS(G,v) ( v is the vertex where the search starts ) Stack S := {}; ( start with an empty stack ) for each vertex u, set visited[u] := false; push S, v; while (S is not empty) do u := pop S; if (not visited[u]) then visited[u] := true; for each unvisited neighbour w of uu push S, w; end if end while END DFS() 

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

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

الآن، لنبدأ بفحص الرسم البياني بدءًا من Node H.

الخطوة 1 - أولاً، ادفع H إلى المكدس.

 STACK: H 

الخطوة 2 - قم بإخراج العنصر العلوي من المكدس، أي H، وقم بطباعته. الآن، ادفع جميع جيران H إلى المكدس الموجود في حالة الاستعداد.

 Print: H]STACK: A 

الخطوه 3 - قم بإخراج العنصر العلوي من المكدس، أي A، وقم بطباعته. الآن، ادفع جميع جيران A إلى المكدس الموجود في حالة الاستعداد.

 Print: A STACK: B, D 

الخطوة 4 - قم بإخراج العنصر العلوي من المكدس، أي D، وقم بطباعته. الآن، ادفع جميع جيران D إلى المكدس الموجود في حالة الاستعداد.

قائمة السهام

 Print: D STACK: B, F 

الخطوة 5 - قم بإخراج العنصر العلوي من المكدس، أي F، وقم بطباعته. الآن، ادفع جميع جيران F إلى المكدس الموجود في حالة الاستعداد.

 Print: F STACK: B 

الخطوة 6 - قم بإخراج العنصر العلوي من المكدس، أي B، وقم بطباعته. الآن، ادفع جميع جيران B إلى المكدس الموجود في حالة الاستعداد.

 Print: B STACK: C 

الخطوة 7 - قم بإخراج العنصر العلوي من المكدس، أي C، وقم بطباعته. الآن، ادفع جميع جيران C إلى المكدس الموجود في حالة الاستعداد.

 Print: C STACK: E, G 

الخطوة 8 - قم بإخراج العنصر العلوي من المكدس، أي G وادفع جميع جيران G إلى المكدس الموجود في حالة الاستعداد.

 Print: G STACK: E 

الخطوة 9 - قم بإخراج العنصر العلوي من المكدس، أي E وادفع جميع العناصر المجاورة لـ E إلى المكدس الموجود في حالة الاستعداد.

 Print: E STACK: 

الآن، تم اجتياز جميع عقد الرسم البياني، والمكدس فارغ.

تعقيد خوارزمية البحث العمق الأول

التعقيد الزمني لخوارزمية DFS هو يا (الخامس + ه) ، حيث V هو عدد القمم وE هو عدد الحواف في الرسم البياني.

التعقيد المكاني لخوارزمية DFS هو O(V).

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

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

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

 /*A sample java program to implement the DFS algorithm*/ import java.util.*; class DFSTraversal { private LinkedList adj[]; /*adjacency list representation*/ private boolean visited[]; /* Creation of the graph */ DFSTraversal(int V) /*&apos;V&apos; is the number of vertices in the graph*/ { adj = new LinkedList[V]; visited = new boolean[V]; for (int i = 0; i <v; i++) adj[i]="new" linkedlist(); } * adding an edge to the graph void insertedge(int src, int dest) { adj[src].add(dest); dfs(int vertex) visited[vertex]="true;" *mark current node as visited* system.out.print(vertex + ' '); iterator it="adj[vertex].listIterator();" while (it.hasnext()) n="it.next();" if (!visited[n]) dfs(n); public static main(string args[]) dfstraversal dfstraversal(8); 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, system.out.println('depth first traversal for is:'); graph.dfs(0); < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/28/dfs-algorithm-3.webp" alt="DFS algorithm"> <h3>Conclusion</h3> <p>In this article, we have discussed the depth-first search technique, its example, complexity, and implementation in the java programming language. Along with that, we have also seen the applications of the depth-first search algorithm.</p> <p>So, that&apos;s all about the article. Hope it will be helpful and informative to you.</p> <hr></v;>