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

1. Lag først en stabel med det totale antallet toppunkter i grafen.
2. Velg nå et hvilket som helst toppunkt som startpunkt for traversering, og skyv det toppunktet inn i stabelen.
3. Etter det skyver du en ikke-besøkt toppunkt (ved siden av toppunktet på toppen av stabelen) til toppen av stabelen.
4. Gjenta nå trinn 3 og 4 til ingen toppunkter er igjen å besøke fra toppunktet på stabelens topp.
5. Hvis det ikke er noe toppunkt igjen, gå tilbake og ta et toppunkt fra stabelen.
6. 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) /*&apos;V&apos; 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&apos;s all about the article. Hope it will be helpful and informative to you.</p> <hr></v;>