במאמר זה, נדון באלגוריתם DFS במבנה הנתונים. זהו אלגוריתם רקורסיבי לחיפוש בכל הקודקודים של מבנה נתוני עץ או גרף. אלגוריתם החיפוש העומק-ראשון (DFS) מתחיל עם הצומת הראשוני של גרף G ומעמיק עד שנמצא את צומת המטרה או הצומת ללא ילדים.
בגלל האופי הרקורסי, ניתן להשתמש במבנה נתונים מחסנית כדי ליישם את אלגוריתם DFS. תהליך הטמעת ה-DFS דומה לאלגוריתם BFS.
התהליך שלב אחר שלב ליישום מעבר DFS ניתן כדלקמן -
- ראשית, צור ערימה עם המספר הכולל של קודקודים בגרף.
- כעת, בחר כל קודקוד כנקודת ההתחלה של המעבר, ודחף את הקודקוד הזה לתוך הערימה.
- לאחר מכן, דחוף קודקוד שלא ביקר (צמוד לקודקוד בראש הערימה) לראש הערימה.
- כעת, חזור על שלבים 3 ו-4 עד שלא נותרו קודקודים לביקור מהקודקוד שבחלק העליון של הערימה.
- אם לא נשאר קודקוד, חזור אחורה והקפיץ קודקוד מהערימה.
- חזור על שלבים 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 קודקודים.
תאריך למחרוזת
כעת, בואו נתחיל לבחון את הגרף החל מ-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.
בדוגמה זו, הגרף שבו אנו משתמשים כדי להדגים את הקוד ניתן באופן הבא -
/*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) /*'V' 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's all about the article. Hope it will be helpful and informative to you.</p> <hr></v;>