In dit artikel bespreken we het DFS-algoritme in de datastructuur. Het is een recursief algoritme om alle hoekpunten van een boomdatastructuur of een grafiek te doorzoeken. Het Depth-First Search (DFS)-algoritme begint met het initiële knooppunt van grafiek G en gaat dieper totdat we het doelknooppunt of het knooppunt zonder kinderen vinden.
Vanwege het recursieve karakter kan de stapelgegevensstructuur worden gebruikt om het DFS-algoritme te implementeren. Het implementatieproces van de DFS is vergelijkbaar met het BFS-algoritme.
Het stapsgewijze proces voor het implementeren van de DFS-traversal wordt als volgt gegeven:
- Maak eerst een stapel met het totale aantal hoekpunten in de grafiek.
- Kies nu een willekeurig hoekpunt als startpunt van de verplaatsing en duw dat hoekpunt in de stapel.
- Duw daarna een niet-bezocht hoekpunt (aangrenzend aan het hoekpunt bovenaan de stapel) naar de bovenkant van de stapel.
- Herhaal nu stap 3 en 4 totdat er geen hoekpunten meer zijn om te bezoeken vanaf het hoekpunt bovenaan de stapel.
- Als er geen hoekpunt meer over is, ga dan terug en knal een hoekpunt uit de stapel.
- Herhaal stap 2, 3 en 4 totdat de stapel leeg is.
Toepassingen van het DFS-algoritme
De toepassingen van het gebruik van het DFS-algoritme worden als volgt gegeven:
- Het DFS-algoritme kan worden gebruikt om de topologische sortering te implementeren.
- Het kan worden gebruikt om de paden tussen twee hoekpunten te vinden.
- Het kan ook worden gebruikt om cycli in de grafiek te detecteren.
- Het DFS-algoritme wordt ook gebruikt voor puzzels met één oplossing.
- DFS wordt gebruikt om te bepalen of een grafiek bipartiet is of niet.
Algoritme
Stap 1: SET STATUS = 1 (gereedstatus) voor elk knooppunt in G
Stap 2: Duw het startknooppunt A op de stapel en stel de STATUS in op 2 (wachtstatus)
Stap 3: Herhaal stap 4 en 5 totdat STACK leeg is
Stap 4: Pop het bovenste knooppunt N. Verwerk het en stel de STATUS in op 3 (verwerkte status)
Stap 5: Duw op de stapel alle buren van N die zich in de gereed-status bevinden (waarvan STATUS = 1) en stel hun STATUS = 2 in (wachtstatus)
[EINDE LUS]
Stap 6: UITGANG
Pseudocode
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() Voorbeeld van een DFS-algoritme
Laten we nu de werking van het DFS-algoritme begrijpen aan de hand van een voorbeeld. In het onderstaande voorbeeld is er een gerichte graaf met 7 hoekpunten.
Laten we nu beginnen met het onderzoeken van de grafiek, beginnend bij Knooppunt H.
java booleaans
Stap 1 - Duw eerst H op de stapel.
STACK: H
Stap 2 - POP het bovenste element van de stapel, d.w.z. H, en druk het af. DRUK nu alle buren van H op de stapel die gereed zijn.
Print: H]STACK: A
Stap 3 - POP het bovenste element van de stapel, d.w.z. A, en druk het af. Duw nu alle buren van A op de stapel die gereed zijn.
Print: A STACK: B, D
Stap 4 - POP het bovenste element van de stapel, d.w.z. D, en druk het af. PUSH nu alle buren van D op de stapel die gereed zijn.
Print: D STACK: B, F
Stap 5 - POP het bovenste element van de stapel, d.w.z. F, en druk het af. PUSH nu alle buren van F op de stapel die gereed zijn.
Print: F STACK: B
Stap 6 - POP het bovenste element van de stapel, d.w.z. B, en druk het af. DRUK nu alle buren van B op de stapel die gereed zijn.
Print: B STACK: C
Stap 7 - POP het bovenste element van de stapel, d.w.z. C, en druk het af. PUSH nu alle buren van C op de stapel die gereed zijn.
Print: C STACK: E, G
Stap 8 - POP het bovenste element van de stapel, d.w.z. G, en PUSH alle buren van G op de stapel die gereed zijn.
Print: G STACK: E
Stap 9 - POP het bovenste element van de stapel, d.w.z. E, en PUSH alle buren van E op de stapel die gereed zijn.
Print: E STACK:
Nu zijn alle grafiekknooppunten doorlopen en is de stapel leeg.
Complexiteit van het Depth-first zoekalgoritme
De tijdscomplexiteit van het DFS-algoritme is O(V+E) , waarbij V het aantal hoekpunten is en E het aantal randen in de grafiek.
De ruimtecomplexiteit van het DFS-algoritme is O(V).
Implementatie van DFS-algoritme
Laten we nu eens kijken naar de implementatie van het DFS-algoritme in Java.
In dit voorbeeld wordt de grafiek die we gebruiken om de code te demonstreren als volgt weergegeven:
/*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;>