V tomto článku budeme diskutovať o algoritme DFS v dátovej štruktúre. Je to rekurzívny algoritmus na vyhľadávanie všetkých vrcholov stromovej dátovej štruktúry alebo grafu. Algoritmus hĺbkového vyhľadávania (DFS) začína počiatočným uzlom grafu G a ide hlbšie, kým nenájdeme cieľový uzol alebo uzol bez potomkov.
Kvôli rekurzívnej povahe možno na implementáciu algoritmu DFS použiť dátovú štruktúru zásobníka. Proces implementácie DFS je podobný algoritmu BFS.
Postup krok za krokom na implementáciu prechodu DFS je uvedený nasledovne -
- Najprv vytvorte zásobník s celkovým počtom vrcholov v grafe.
- Teraz vyberte ľubovoľný vrchol ako počiatočný bod prechodu a zatlačte tento vrchol do zásobníka.
- Potom zatlačte nenavštívený vrchol (susediaci s vrcholom na vrchu zásobníka) na vrchol zásobníka.
- Teraz opakujte kroky 3 a 4, kým nezostanú žiadne vrcholy, ktoré by ste mohli navštíviť z vrcholu na vrchu zásobníka.
- Ak nezostane žiadny vrchol, vráťte sa a vyberte vrchol zo zásobníka.
- Opakujte kroky 2, 3 a 4, kým nebude zásobník prázdny.
Aplikácie algoritmu DFS
Aplikácie použitia algoritmu DFS sú uvedené nasledovne -
mvc pre java
- Algoritmus DFS možno použiť na implementáciu topologického triedenia.
- Môže sa použiť na nájdenie ciest medzi dvoma vrcholmi.
- Dá sa použiť aj na detekciu cyklov v grafe.
- Algoritmus DFS sa používa aj pre hádanky s jedným riešením.
- DFS sa používa na určenie, či je graf bipartitný alebo nie.
Algoritmus
Krok 1: SET STATUS = 1 (stav pripravenosti) pre každý uzol v G
Krok 2: Zatlačte počiatočný uzol A na zásobník a nastavte jeho STAV = 2 (stav čakania)
Krok 3: Opakujte kroky 4 a 5, kým nebude STACK prázdny
Krok 4: Vyberte horný uzol N. Spracujte ho a nastavte jeho STAV = 3 (stav spracovania)
Krok 5: Zatlačte na zásobník všetkých susedov N, ktorí sú v stave pripravenosti (ktorých STATUS = 1) a nastavte ich STATUS = 2 (čakajúci stav)
[KONIEC SLUČKY]
Krok 6: VÝCHOD
Pseudokód
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() Príklad algoritmu DFS
Teraz pochopme fungovanie algoritmu DFS pomocou príkladu. V nižšie uvedenom príklade je orientovaný graf so 7 vrcholmi.
Teraz začnime skúmať graf počnúc uzlom H.
Krok 1 - Najprv zatlačte H na stoh.
funkcie v c
STACK: H
Krok 2 - Vyberte horný prvok zo zásobníka, t. j. H, a vytlačte ho. Teraz PUSH všetkých susedov H do zásobníka, ktorí sú v stave pripravenosti.
Print: H]STACK: A
Krok 3 - Vyberte horný prvok zo zásobníka, t. j. A, a vytlačte ho. Teraz PUSH všetkých susedov A do zásobníka, ktorí sú v pripravenom stave.
Print: A STACK: B, D
Krok 4 - Vysuňte horný prvok zo stohu, t. j. D, a vytlačte ho. Teraz PUSH všetkých susedov D do zásobníka, ktorí sú v pripravenom stave.
Print: D STACK: B, F
Krok 5 - Vyberte horný prvok zo zásobníka, t. j. F, a vytlačte ho. Teraz PUSH všetkých susedov F do zásobníka, ktorí sú v stave pripravenosti.
Print: F STACK: B
Krok 6 - Vyberte horný prvok zo zásobníka, t. j. B, a vytlačte ho. Teraz PUSH všetkých susedov B na zásobník, ktorí sú v stave pripravenosti.
Print: B STACK: C
Krok 7 - Vyberte horný prvok zo zásobníka, t. j. C, a vytlačte ho. Teraz PUSH všetkých susedov C do zásobníka, ktorí sú v stave pripravenosti.
Print: C STACK: E, G
Krok 8 - Vysuňte horný prvok zo zásobníka, t.j. G a PUSH všetkých susedov G na zásobník, ktorý je v stave pripravenosti.
Print: G STACK: E
Krok 9 - Vysuňte horný prvok zo stohu, t. j. E a PUSH všetkých susedov E do stohu, ktoré sú v stave pripravenosti.
Print: E STACK:
Teraz sa prešli všetky uzly grafu a zásobník je prázdny.
príkaz chown
Zložitosť algoritmu hĺbkového vyhľadávania
Časová zložitosť algoritmu DFS je O(V+E) , kde V je počet vrcholov a E je počet hrán v grafe.
Priestorová zložitosť algoritmu DFS je O(V).
Implementácia DFS algoritmu
Teraz sa pozrime na implementáciu algoritmu DFS v jazyku Java.
V tomto príklade je graf, ktorý používame na demonštráciu kódu, uvedený takto -
/*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;>