logo

TechCodeview

אלגוריתם DFS (Depth First Search).

במאמר זה, נדון באלגוריתם 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. עבד אותו והגדר את STATUS שלו = 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 קודקודים.

תאריך למחרוזת
אלגוריתם DFS

כעת, בואו נתחיל לבחון את הגרף החל מ-Node H.

שלב 1 - ראשית, דחפו את H על הערימה.

 STACK: H

שלב 2 - POP את האלמנט העליון מהערימה, כלומר, H, והדפיס אותו. כעת, דחוף את כל השכנים של H אל המחסנית שנמצאים במצב מוכן.

 Print: H]STACK: A

שלב 3 - POP את האלמנט העליון מהערימה, כלומר, A, והדפיס אותו. כעת, דחוף את כל השכנים של A אל המחסנית שנמצאים במצב מוכן.

 Print: A STACK: B, D

שלב 4 - POP את האלמנט העליון מהערימה, כלומר, D, והדפיס אותו. כעת, דחוף את כל השכנים של D אל המחסנית שנמצאים במצב מוכן.

 Print: D STACK: B, F

שלב 5 - POP את האלמנט העליון מהערימה, כלומר F, והדפיס אותו. כעת, דחוף את כל השכנים של F לערימה שנמצאים במצב מוכן.

 Print: F STACK: B

שלב 6 - POP את האלמנט העליון מהערימה, כלומר B, והדפיס אותו. כעת, דחוף את כל השכנים של B אל המחסנית שנמצאים במצב מוכן.

 Print: B STACK: C

שלב 7 - POP את האלמנט העליון מהערימה, כלומר, C, והדפיס אותו. כעת, דחוף את כל השכנים של C אל המחסנית שנמצאים במצב מוכן.

 Print: C STACK: E, G

שלב 8 - POP את האלמנט העליון מהמחסנית, כלומר, G ודחף את כל השכנים של G אל המחסנית שנמצאים במצב מוכן.

 Print: G STACK: E

שלב 9 - POP את האלמנט העליון מהמחסנית, כלומר, E ודחף את כל השכנים של E על המחסנית שנמצאים במצב מוכן.

 Print: E STACK:

כעת, כל צמתי הגרף עברו, והערימה ריקה.

המורכבות של אלגוריתם חיפוש עומק ראשון

מורכבות הזמן של אלגוריתם DFS היא O(V+E) , כאשר V הוא מספר הקודקודים ו-E הוא מספר הקצוות בגרף.

מורכבות החלל של אלגוריתם DFS היא O(V).

יישום אלגוריתם DFS

כעת, בואו נראה את היישום של אלגוריתם DFS ב-Java.

בדוגמה זו, הגרף שבו אנו משתמשים כדי להדגים את הקוד ניתן באופן הבא -

אלגוריתם 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;>