En aquest article, parlarem de l'algorisme DFS a l'estructura de dades. És un algorisme recursiu per cercar tots els vèrtexs d'una estructura de dades d'arbre o d'un gràfic. L'algorisme de cerca en profunditat (DFS) comença amb el node inicial del gràfic G i s'aprofundeix fins que trobem el node objectiu o el node sense fills.
A causa de la naturalesa recursiva, l'estructura de dades de pila es pot utilitzar per implementar l'algorisme DFS. El procés d'implementació del DFS és similar a l'algorisme BFS.
El procés pas a pas per implementar el recorregut DFS es mostra de la següent manera:
- Primer, creeu una pila amb el nombre total de vèrtexs del gràfic.
- Ara, trieu qualsevol vèrtex com a punt de partida de la travessa i introduïu aquest vèrtex a la pila.
- Després d'això, empeny un vèrtex no visitat (adjacent al vèrtex de la part superior de la pila) a la part superior de la pila.
- Ara, repetiu els passos 3 i 4 fins que no quedi cap vèrtex per visitar des del vèrtex de la part superior de la pila.
- Si no queda cap vèrtex, torna enrere i treu un vèrtex de la pila.
- Repetiu els passos 2, 3 i 4 fins que la pila estigui buida.
Aplicacions de l'algorisme DFS
Les aplicacions per utilitzar l'algorisme DFS es donen de la següent manera:
- L'algorisme DFS es pot utilitzar per implementar l'ordenació topològica.
- Es pot utilitzar per trobar els camins entre dos vèrtexs.
- També es pot utilitzar per detectar cicles en el gràfic.
- L'algorisme DFS també s'utilitza per a trencaclosques d'una solució.
- DFS s'utilitza per determinar si un gràfic és bipartit o no.
Algorisme
Pas 1: SET STATUS = 1 (estat preparat) per a cada node de G
Pas 2: Premeu el node inicial A a la pila i configureu el seu STATUS = 2 (estat d'espera)
Pas 3: Repetiu els passos 4 i 5 fins que la PILA estigui buida
Pas 4: Obre el node superior N. Processa'l i defineix el seu STATUS = 3 (estat processat)
Pas 5: Premeu a la pila tots els veïns de N que es troben a l'estat preparat (l'estat dels quals = 1) i establiu el seu STATUS = 2 (estat d'espera)
[FI DEL BULE]
Pas 6: SORTIR
Pseudocodi
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() Exemple d'algorisme DFS
Ara, anem a comprendre el funcionament de l'algorisme DFS utilitzant un exemple. En l'exemple que es mostra a continuació, hi ha un gràfic dirigit amb 7 vèrtexs.
Ara, comencem a examinar el gràfic a partir del node H.
cadena de comparació de java
Pas 1 - Primer, premeu H a la pila.
STACK: H
Pas 2 - OPLICA l'element superior de la pila, és a dir, H, i imprimeix-lo. Ara, empeny tots els veïns de H a la pila que es troben en estat llest.
Print: H]STACK: A
Pas 3 - OUP l'element superior de la pila, és a dir, A, i imprimiu-lo. Ara, empeny tots els veïns d'A a la pila que es troben en estat preparat.
Print: A STACK: B, D
Pas 4 - OUP l'element superior de la pila, és a dir, D, i imprimiu-lo. Ara, empeny tots els veïns de D a la pila que es troben en estat llest.
exemple de dades json
Print: D STACK: B, F
Pas 5 - OBRE l'element superior de la pila, és a dir, F, i imprimiu-lo. Ara, empeny tots els veïns de F a la pila que es troben en estat llest.
Print: F STACK: B
Pas 6 - OUP l'element superior de la pila, és a dir, B, i imprimiu-lo. Ara, empeny tots els veïns de B a la pila que es troben en estat llest.
Print: B STACK: C
Pas 7 - POP l'element superior de la pila, és a dir, C, i imprimiu-lo. Ara, empeny tots els veïns de C a la pila que es troben en estat llest.
Print: C STACK: E, G
Pas 8 - POP l'element superior de la pila, és a dir, G i PUSH tots els veïns de G a la pila que estan en estat preparat.
Print: G STACK: E
Pas 9 - POP l'element superior de la pila, és a dir, E i PUSH tots els veïns d'E a la pila que estan en estat preparat.
Print: E STACK:
Ara, s'han travessat tots els nodes del gràfic i la pila està buida.
Complexitat de l'algoritme de cerca en profunditat
La complexitat temporal de l'algorisme DFS és O(V+E) , on V és el nombre de vèrtexs i E és el nombre d'arestes del gràfic.
La complexitat espacial de l'algorisme DFS és O(V).
Implementació de l'algorisme DFS
Ara, vegem la implementació de l'algorisme DFS a Java.
En aquest exemple, el gràfic que estem utilitzant per demostrar el codi es dóna de la següent manera:
/*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;>