logo

TechCodeview

DFS (Depth First Search) algoritam

U ovom ćemo članku raspravljati o DFS algoritmu u strukturi podataka. To je rekurzivni algoritam za pretraživanje svih vrhova podatkovne strukture stabla ili grafa. Algoritam pretraživanja u dubinu (DFS) počinje s početnim čvorom grafa G i ide dublje dok ne pronađemo ciljni čvor ili čvor bez djece.

Zbog rekurzivne prirode, struktura podataka stog može se koristiti za implementaciju DFS algoritma. Proces implementacije DFS-a sličan je BFS algoritmu.

Korak po korak proces implementacije DFS traversal-a dan je kako slijedi -

  1. Prvo stvorite hrpu s ukupnim brojem vrhova u grafu.
  2. Sada odaberite bilo koji vrh kao početnu točku obilaska i gurnite taj vrh u stog.
  3. Nakon toga gurnite neposjećeni vrh (susjedni vrha na vrhu snopa) na vrh snopa.
  4. Sada ponovite korake 3 i 4 dok ne preostane nijedan vrh koji bi se mogao posjetiti iz vrha na vrhu hrpe.
  5. Ako nema preostalog vrha, vratite se i izvadite vrh iz hrpe.
  6. Ponavljajte korake 2, 3 i 4 dok se hrpa ne isprazni.

Primjene DFS algoritma

Primjene korištenja DFS algoritma date su kako slijedi -

kako blokirati youtube oglase na androidu
  • DFS algoritam se može koristiti za implementaciju topološkog sortiranja.
  • Može se koristiti za pronalaženje staza između dva vrha.
  • Također se može koristiti za otkrivanje ciklusa u grafikonu.
  • DFS algoritam se također koristi za zagonetke s jednim rješenjem.
  • DFS se koristi za određivanje je li graf bipartitan ili ne.

Algoritam

Korak 1: SET STATUS = 1 (stanje spremno) za svaki čvor u G

Korak 2: Gurnite početni čvor A na stog i postavite mu STATUS = 2 (stanje čekanja)

Korak 3: Ponavljajte korake 4 i 5 dok se STAK ne isprazni

Korak 4: Otvorite gornji čvor N. Obradite ga i postavite mu STATUS = 3 (obrađeno stanje)

Korak 5: Gurnite na stog sve susjede od N koji su u stanju spremnosti (čiji STATUS = 1) i postavite njihov STATUS = 2 (stanje čekanja)

[KRAJ PETLJE]

Korak 6: IZLAZ

Pseudokod

 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()

Primjer DFS algoritma

Razmotrimo sada rad DFS algoritma pomoću primjera. U donjem primjeru postoji usmjereni graf koji ima 7 vrhova.

DFS algoritam

Sada, počnimo ispitivati ​​graf počevši od čvora H.

Korak 1 - Prvo gurnite H na hrpu.

 STACK: H

Korak 2 - Iskočite gornji element iz hrpe, tj. H, i ispišite ga. Sada gurnite sve susjede od H na stog koji su u stanju pripravnosti.

 Print: H]STACK: A

3. korak - Iskočite gornji element iz hrpe, tj. A, i ispišite ga. Sada, GURNITE sve susjede A na stog koji su u stanju pripravnosti.

 Print: A STACK: B, D

Korak 4 - Iskočite gornji element iz hrpe, tj. D, i ispišite ga. Sada, GURNITE sve susjede od D na stog koji su u stanju pripravnosti.

bash nizovi 
 Print: D STACK: B, F

Korak 5 - Iskočite gornji element iz hrpe, tj. F, i ispišite ga. Sada, GURNITE sve susjede F na stog koji su u stanju pripravnosti.

 Print: F STACK: B

Korak 6 - Iskočite gornji element iz hrpe, tj. B, i ispišite ga. Sada, GURNITE sve susjede B na stog koji su u stanju pripravnosti.

 Print: B STACK: C

Korak 7 - Iskočite gornji element iz hrpe, tj. C, i ispišite ga. Sada gurnite sve susjede od C na stog koji su u stanju pripravnosti.

 Print: C STACK: E, G

Korak 8 - ISKOČITE gornji element sa stoga, tj. G i gurnite sve susjede G na stog koji su u stanju pripravnosti.

 Print: G STACK: E

Korak 9 - Iskočite gornji element iz stoga, tj. E i gurnite sve susjede E na stog koji su u stanju pripravnosti.

 Print: E STACK:

Sada su svi čvorovi grafa prošli, a stog je prazan.

Složenost algoritma pretraživanja prve dubine

Vremenska složenost DFS algoritma je O(V+E) , gdje je V broj vrhova, a E broj bridova u grafu.

Prostorna složenost DFS algoritma je O(V).

Implementacija DFS algoritma

Sada, da vidimo implementaciju DFS algoritma u Javi.

U ovom primjeru, grafikon koji koristimo za demonstraciju koda dan je kako slijedi -

DFS algoritam 
 /*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;>