In questo articolo discuteremo dell'algoritmo DFS nella struttura dei dati. È un algoritmo ricorsivo per cercare tutti i vertici di una struttura dati ad albero o di un grafico. L'algoritmo di ricerca in profondità (DFS) inizia con il nodo iniziale del grafo G e va più in profondità finché non troviamo il nodo obiettivo o il nodo senza figli.
A causa della natura ricorsiva, la struttura dei dati dello stack può essere utilizzata per implementare l'algoritmo DFS. Il processo di implementazione del DFS è simile all'algoritmo BFS.
Il processo passo passo per implementare l'attraversamento DFS è il seguente:
- Innanzitutto, crea uno stack con il numero totale di vertici nel grafico.
- Ora scegli un vertice qualsiasi come punto iniziale dell'attraversamento e inserisci quel vertice nello stack.
- Successivamente, spingi un vertice non visitato (adiacente al vertice in cima allo stack) in cima allo stack.
- Ora ripeti i passaggi 3 e 4 finché non rimangono più vertici da visitare dal vertice in cima allo stack.
- Se non rimane alcun vertice, torna indietro e prendi un vertice dalla pila.
- Ripetere i passaggi 2, 3 e 4 finché lo stack non sarà vuoto.
Applicazioni dell'algoritmo DFS
Le applicazioni dell'utilizzo dell'algoritmo DFS sono fornite come segue:
- L'algoritmo DFS può essere utilizzato per implementare l'ordinamento topologico.
- Può essere utilizzato per trovare i percorsi tra due vertici.
- Può anche essere utilizzato per rilevare cicli nel grafico.
- L'algoritmo DFS viene utilizzato anche per i puzzle a una soluzione.
- DFS viene utilizzato per determinare se un grafico è bipartito o meno.
Algoritmo
Passo 1: SET STATUS = 1 (stato pronto) per ciascun nodo in G
come bloccare gli annunci di YouTube su Android
Passo 2: Spingi il nodo iniziale A nello stack e imposta il suo STATUS = 2 (stato di attesa)
Passaggio 3: Ripetere i passaggi 4 e 5 finché lo STACK non sarà vuoto
Passaggio 4: Apri il nodo superiore N. Elaboralo e imposta il suo STATUS = 3 (stato elaborato)
Passaggio 5: Metti nello stack tutti i vicini di N che sono nello stato pronto (il cui STATUS = 1) e imposta il loro STATUS = 2 (stato di attesa)
[FINE DEL CICLO]
Passaggio 6: USCITA
array di programmazione Java
Pseudocodice
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() Esempio di algoritmo DFS
Ora comprendiamo il funzionamento dell'algoritmo DFS utilizzando un esempio. Nell'esempio riportato di seguito, esiste un grafico diretto con 7 vertici.
Iniziamo ora ad esaminare il grafico partendo dal Nodo H.
Passo 1 - Per prima cosa, metti H nella pila.
polimorfismo Java
STACK: H
Passo 2 - POP l'elemento in cima allo stack, cioè H, e stampalo. Ora, SPINGI tutti i vicini di H nello stack che sono nello stato pronto.
Print: H]STACK: A
Passaggio 3 - POP l'elemento in cima allo stack, cioè A, e stampalo. Ora, SPINGI tutti i vicini di A nello stack che sono nello stato pronto.
Print: A STACK: B, D
Passaggio 4 - POP l'elemento in cima allo stack, cioè D, e stampalo. Ora, SPINGI tutti i vicini di D nello stack che sono nello stato pronto.
Print: D STACK: B, F
Passaggio 5 - POP l'elemento in cima allo stack, cioè F, e stampalo. Ora, SPINGI tutti i vicini di F nello stack che sono nello stato pronto.
Print: F STACK: B
Passaggio 6 - POP l'elemento in cima allo stack, cioè B, e stampalo. Ora, SPINGI tutti i vicini di B nello stack che sono nello stato pronto.
Print: B STACK: C
Passaggio 7 - POP l'elemento in cima allo stack, cioè C, e stampalo. Ora, SPINGI tutti i vicini di C nello stack che sono nello stato pronto.
preity zinta
Print: C STACK: E, G
Passaggio 8 - POP l'elemento in cima allo stack, cioè G e PUSH tutti gli elementi vicini di G nello stack che sono nello stato pronto.
Print: G STACK: E
Passaggio 9 - POP l'elemento in cima allo stack, cioè E, e PUSH tutti gli elementi vicini di E nello stack che sono nello stato pronto.
Print: E STACK:
Ora tutti i nodi del grafico sono stati attraversati e lo stack è vuoto.
Complessità dell'algoritmo di ricerca Depth-first
La complessità temporale dell'algoritmo DFS è O(V+E) , dove V è il numero di vertici ed E è il numero di archi nel grafico.
La complessità spaziale dell'algoritmo DFS è O(V).
Implementazione dell'algoritmo DFS
Ora vediamo l'implementazione dell'algoritmo DFS in Java.
In questo esempio, il grafico che stiamo utilizzando per dimostrare il codice è dato come segue:
/*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;>