În acest articol, vom discuta despre algoritmul DFS în structura datelor. Este un algoritm recursiv pentru a căuta toate nodurile unei structuri de date arborescente sau ale unui grafic. Algoritmul de căutare în profunzime (DFS) începe cu nodul inițial al graficului G și merge mai adânc până când găsim nodul obiectiv sau nodul fără copii.
Datorită naturii recursive, structura de date a stivei poate fi utilizată pentru a implementa algoritmul DFS. Procesul de implementare a DFS este similar cu algoritmul BFS.
Procesul pas cu pas pentru implementarea traversării DFS este prezentat după cum urmează -
- Mai întâi, creați o stivă cu numărul total de vârfuri din grafic.
- Acum, alegeți orice vârf ca punct de plecare al traversării și împingeți acel vârf în stivă.
- După aceea, împingeți un vârf nevizitat (adiacent vârfului din partea de sus a stivei) în partea de sus a stivei.
- Acum, repetați pașii 3 și 4 până când nu mai rămân vârfuri de vizitat de la vârful din vârful stivei.
- Dacă nu mai rămâne niciun vârf, întoarceți-vă și scoateți un vârf din stivă.
- Repetați pașii 2, 3 și 4 până când stiva este goală.
Aplicații ale algoritmului DFS
Aplicațiile utilizării algoritmului DFS sunt prezentate după cum urmează -
- Algoritmul DFS poate fi utilizat pentru a implementa sortarea topologică.
- Poate fi folosit pentru a găsi căile dintre două vârfuri.
- Poate fi folosit și pentru a detecta ciclurile din grafic.
- Algoritmul DFS este folosit și pentru puzzle-uri cu o soluție.
- DFS este utilizat pentru a determina dacă un grafic este bipartit sau nu.
Algoritm
Pasul 1: SET STATUS = 1 (stare gata) pentru fiecare nod din G
Pasul 2: Apăsați nodul de pornire A pe stivă și setați-i STATUS = 2 (starea de așteptare)
Pasul 3: Repetați pașii 4 și 5 până când STACK este gol
char la șir în java
Pasul 4: Pop nodul superior N. Procesați-l și setați-i STATUS = 3 (starea procesată)
Pasul 5: Apăsați pe stivă toți vecinii lui N care sunt în starea pregătită (a căror STARE = 1) și setați-le STARE = 2 (starea de așteptare)
[Sfârșitul buclei]
Pasul 6: IEȘIRE
Pseudo cod
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() Exemplu de algoritm DFS
Acum, să înțelegem funcționarea algoritmului DFS folosind un exemplu. În exemplul de mai jos, există un grafic direcționat având 7 vârfuri.
Acum, să începem să examinăm graficul pornind de la Nodul H.
Pasul 1 - Mai întâi, împingeți H pe stivă.
java localdatetime
STACK: H
Pasul 2 - POP elementul de sus din stivă, adică H, și imprimați-l. Acum, împingeți toți vecinii lui H pe stiva care sunt în stare gata.
Print: H]STACK: A
Pasul 3 - POP elementul de sus din stivă, adică A, și imprimați-l. Acum, împingeți toți vecinii lui A pe stiva care sunt în stare gata.
Print: A STACK: B, D
Pasul 4 - POP elementul de sus din stivă, adică D, și imprimați-l. Acum, împingeți toți vecinii lui D pe stiva care sunt în stare gata.
Print: D STACK: B, F
Pasul 5 - POP elementul de sus din stivă, adică F, și imprimați-l. Acum, împingeți toți vecinii lui F pe stiva care sunt în stare gata.
Print: F STACK: B
Pasul 6 - POP elementul de sus din stivă, adică B, și imprimați-l. Acum, împingeți toți vecinii lui B pe stiva care sunt în stare gata.
Print: B STACK: C
Pasul 7 - POP elementul de sus din stivă, adică C, și imprimați-l. Acum, împingeți toți vecinii lui C pe stiva care sunt în stare gata.
Print: C STACK: E, G
Pasul 8 - POP elementul de sus din stivă, adică G și împingeți toți vecinii lui G pe stiva care sunt în stare gata.
Print: G STACK: E
Pasul 9 - POP elementul de sus din stivă, adică E și împingeți toți vecinii lui E pe stiva care sunt în stare gata.
Print: E STACK:
Acum, toate nodurile graficului au fost parcurse, iar stiva este goală.
ctc formă completă
Complexitatea algoritmului de căutare în profunzime
Complexitatea de timp a algoritmului DFS este O(V+E) , unde V este numărul de vârfuri și E este numărul de muchii din grafic.
Complexitatea spațială a algoritmului DFS este O(V).
Implementarea algoritmului DFS
Acum, să vedem implementarea algoritmului DFS în Java.
În acest exemplu, graficul pe care îl folosim pentru a demonstra codul este dat după cum urmează -
/*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;>