logo

TechCodeview

Algoritem DFS (Depth First Search).

V tem članku bomo razpravljali o algoritmu DFS v strukturi podatkov. Je rekurziven algoritem za iskanje po vseh točkah drevesne podatkovne strukture ali grafa. Algoritem iskanja v globino (DFS) se začne z začetnim vozliščem grafa G in gre globlje, dokler ne najdemo ciljnega vozlišča ali vozlišča brez otrok.

Zaradi rekurzivne narave lahko strukturo podatkov sklada uporabimo za implementacijo algoritma DFS. Postopek implementacije DFS je podoben algoritmu BFS.

Postopek po korakih za implementacijo prečkanja DFS je podan na naslednji način -

funkcija java podniz
  1. Najprej ustvarite sklad s skupnim številom vozlišč v grafu.
  2. Sedaj izberite katero koli točko kot začetno točko prečkanja in to točko potisnite v sklad.
  3. Po tem potisnite neobiskano točko (sosednjo točko na vrhu sklada) na vrh sklada.
  4. Zdaj ponovite koraka 3 in 4, dokler ne ostane nobena točka, ki bi jo lahko obiskali iz točke na vrhu sklada.
  5. Če ni več nobene točke, se vrnite in odstranite točko iz sklada.
  6. Ponavljajte korake 2, 3 in 4, dokler sveženj ni prazen.

Uporaba algoritma DFS

Aplikacije uporabe algoritma DFS so podane na naslednji način -

  • Za izvedbo topološkega razvrščanja se lahko uporabi algoritem DFS.
  • Uporablja se lahko za iskanje poti med dvema vozliščema.
  • Uporablja se lahko tudi za zaznavanje ciklov v grafu.
  • Algoritem DFS se uporablja tudi za uganke z eno rešitvijo.
  • DFS se uporablja za ugotavljanje, ali je graf bipartiten ali ne.

Algoritem

Korak 1: SET STATUS = 1 (stanje pripravljenosti) za vsako vozlišče v G

2. korak: Potisnite začetno vozlišče A na sklad in nastavite STATUS = 2 (čakalno stanje)

3. korak: Ponavljajte koraka 4 in 5, dokler ni STACK prazen

4. korak: Odprite zgornje vozlišče N. Obdelajte ga in mu nastavite STATUS = 3 (obdelano stanje)

5. korak: Potisnite na sklad vse sosede N, ki so v stanju pripravljenosti (katerih STATUS = 1) in nastavite njihov STATUS = 2 (stanje čakanja)

[KONEC ZANKE]

6. korak: IZHOD

Psevdokoda

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

Primer algoritma DFS

Zdaj pa na primeru razumejmo delovanje algoritma DFS. V spodnjem primeru je usmerjen graf s 7 vozlišči.

DFS algoritem

Zdaj pa začnimo preučevati graf, začenši z vozliščem H.

Korak 1 - Najprej potisnite H na sklad.

 STACK: H

2. korak - Izstopite zgornji element iz sklada, tj. H, in ga natisnite. Zdaj pa PUSH vse sosede H na sklad, ki so v stanju pripravljenosti.

 Print: H]STACK: A

3. korak - Izstopite zgornji element iz sklada, tj. A, in ga natisnite. Zdaj pa PUSH vse sosede A na sklad, ki so v stanju pripravljenosti.

 Print: A STACK: B, D

4. korak - Izstopite zgornji element iz sklada, tj. D, in ga natisnite. Zdaj pa PUSH vse sosede D na sklad, ki so v stanju pripravljenosti.

iterator java zemljevid 
 Print: D STACK: B, F

5. korak - POP zgornji element iz sklada, tj. F, in ga natisnite. Zdaj pa PUSH vse sosede F na sklad, ki so v stanju pripravljenosti.

 Print: F STACK: B

6. korak - Izstopite zgornji element iz sklada, tj. B, in ga natisnite. Zdaj pa PUSH vse sosede B na sklad, ki so v stanju pripravljenosti.

 Print: B STACK: C

korak 7 - POP zgornji element iz sklada, tj. C, in ga natisnite. Zdaj pa PUSH vse sosede C na sklad, ki so v stanju pripravljenosti.

 Print: C STACK: E, G

8. korak - POP zgornji element iz sklada, tj. G in PUSH vse sosede G na sklad, ki so v stanju pripravljenosti.

 Print: G STACK: E

9. korak - POP zgornji element iz sklada, tj. E in PUSH vse sosede E na sklad, ki so v stanju pripravljenosti.

 Print: E STACK:

Zdaj so bila prečkana vsa vozlišča grafa in sklad je prazen.

Kompleksnost algoritma iskanja v globino

Časovna zahtevnost algoritma DFS je O(V+E) , kjer je V število vozlišč in E število robov v grafu.

Prostorska kompleksnost algoritma DFS je O(V).

Implementacija algoritma DFS

Zdaj pa si oglejmo implementacijo algoritma DFS v Javi.

V tem primeru je graf, ki ga uporabljamo za predstavitev kode, podan na naslednji način -

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