I denne artikkelen vil vi diskutere DFS-algoritmen i datastrukturen. Det er en rekursiv algoritme for å søke i alle toppunktene i en tredatastruktur eller en graf. Dybde-først-søk-algoritmen (DFS) starter med den innledende noden til graf G og går dypere til vi finner målnoden eller noden uten barn.
På grunn av den rekursive naturen kan stackdatastrukturen brukes til å implementere DFS-algoritmen. Prosessen med å implementere DFS ligner på BFS-algoritmen.
Den trinnvise prosessen for å implementere DFS-gjennomgangen er gitt som følger -
cast int til streng java
- Lag først en stabel med det totale antallet toppunkter i grafen.
- Velg nå et hvilket som helst toppunkt som startpunkt for traversering, og skyv det toppunktet inn i stabelen.
- Etter det skyver du en ikke-besøkt toppunkt (ved siden av toppunktet på toppen av stabelen) til toppen av stabelen.
- Gjenta nå trinn 3 og 4 til ingen toppunkter er igjen å besøke fra toppunktet på stabelens topp.
- Hvis det ikke er noe toppunkt igjen, gå tilbake og ta et toppunkt fra stabelen.
- Gjenta trinn 2, 3 og 4 til stabelen er tom.
Anvendelser av DFS-algoritme
Applikasjonene for å bruke DFS-algoritmen er gitt som følger -
- DFS-algoritmen kan brukes til å implementere den topologiske sorteringen.
- Den kan brukes til å finne banene mellom to hjørner.
- Den kan også brukes til å oppdage sykluser i grafen.
- DFS-algoritme brukes også for én løsningsoppgaver.
- DFS brukes til å bestemme om en graf er todelt eller ikke.
Algoritme
Trinn 1: SET STATUS = 1 (klar tilstand) for hver node i G
Steg 2: Skyv startnoden A på stabelen og sett dens STATUS = 2 (ventetilstand)
Trinn 3: Gjenta trinn 4 og 5 til STABLEN er tom
Trinn 4: Pop den øverste noden N. Behandle den og sett dens STATUS = 3 (behandlet tilstand)
Trinn 5: Skyv på stabelen alle naboene til N som er i klartilstand (hvis STATUS = 1) og sett deres STATUS = 2 (ventetilstand)
[SLUTT PÅ LOOP]
Trinn 6: EXIT
javafx
Pseudokode
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() Eksempel på DFS-algoritme
La oss nå forstå hvordan DFS-algoritmen fungerer ved å bruke et eksempel. I eksemplet nedenfor er det en rettet graf med 7 toppunkter.
La oss nå begynne å undersøke grafen fra Node H.
Trinn 1 - Først skyver du H på stabelen.
navn på usa by
STACK: H
Steg 2 - POP det øverste elementet fra stabelen, dvs. H, og skriv det ut. Skyv nå alle naboene til H inn på stabelen som er i klar tilstand.
Print: H]STACK: A
Trinn 3 - POP det øverste elementet fra stabelen, dvs. A, og skriv det ut. Skyv nå alle naboene til A på stabelen som er klar.
Print: A STACK: B, D
Trinn 4 - POP det øverste elementet fra stabelen, dvs. D, og skriv det ut. Skyv nå alle naboene til D inn på stabelen som er i klar tilstand.
Print: D STACK: B, F
Trinn 5 - POP det øverste elementet fra stabelen, dvs. F, og skriv det ut. Skyv nå alle naboene til F på stabelen som er i klar tilstand.
Print: F STACK: B
Trinn 6 - POP det øverste elementet fra stabelen, dvs. B, og skriv det ut. Skyv nå alle naboene til B på stabelen som er i klar tilstand.
Print: B STACK: C
Trinn 7 - POP det øverste elementet fra stabelen, dvs. C, og skriv det ut. Skyv nå alle naboene til C på stabelen som er i klar tilstand.
Print: C STACK: E, G
Trinn 8 - POP det øverste elementet fra stabelen, dvs. G og SKYV alle naboene til G på stabelen som er i klar tilstand.
Print: G STACK: E
Trinn 9 - POP det øverste elementet fra stabelen, dvs. E og SKYV alle naboene til E på stabelen som er i klar tilstand.
Print: E STACK:
Nå har alle grafnodene blitt krysset, og stabelen er tom.
Kompleksiteten til Depth-first-søkealgoritmen
Tidskompleksiteten til DFS-algoritmen er O(V+E) , hvor V er antall toppunkter og E er antall kanter i grafen.
strengmetoder java
Romkompleksiteten til DFS-algoritmen er O(V).
Implementering av DFS-algoritme
La oss nå se implementeringen av DFS-algoritmen i Java.
I dette eksemplet er grafen som vi bruker for å demonstrere koden gitt som følger -
/*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;>