logo

TechCodeview

DFS (Depth First Search) algoritms

Šajā rakstā mēs apspriedīsim DFS algoritmu datu struktūrā. Tas ir rekursīvs algoritms, lai meklētu visas koka datu struktūras vai grafa virsotnes. Pirmās dziļuma meklēšanas (DFS) algoritms sākas ar grafa G sākotnējo mezglu un iet dziļāk, līdz atrodam mērķa mezglu vai mezglu bez bērniem.

Rekursīvā rakstura dēļ steka datu struktūru var izmantot, lai ieviestu DFS algoritmu. DFS ieviešanas process ir līdzīgs BFS algoritmam.

Soli pa solim process, lai ieviestu DFS šķērsošanu, ir norādīts šādi:

  1. Vispirms izveidojiet kaudzi ar kopējo virsotņu skaitu grafikā.
  2. Tagad izvēlieties jebkuru virsotni kā šķērsošanas sākumpunktu un iespiediet šo virsotni kaudzē.
  3. Pēc tam virziet neapmeklētu virsotni (blakus virsotnei kaudzes augšpusē) uz kaudzes augšdaļu.
  4. Tagad atkārtojiet 3. un 4. darbību, līdz vairs nav nevienas virsotnes, ko apmeklēt no virsotnes kaudzes augšpusē.
  5. Ja neviena virsotne nav atstāta, dodieties atpakaļ un izvelciet virsotni no steka.
  6. Atkārtojiet 2., 3. un 4. darbību, līdz kaudze ir tukša.

DFS algoritma pielietojumi

DFS algoritma izmantošanas pielietojumi ir doti šādi:

  • DFS algoritmu var izmantot, lai īstenotu topoloģisko šķirošanu.
  • To var izmantot, lai atrastu ceļus starp divām virsotnēm.
  • To var izmantot arī ciklu noteikšanai grafikā.
  • DFS algoritms tiek izmantots arī viena risinājuma mīklām.
  • DFS tiek izmantots, lai noteiktu, vai grafiks ir divpusējs vai nē.

Algoritms

1. darbība: SET STATUS = 1 (gatavības stāvoklis) katram G mezglam

2. darbība: Nospiediet sākuma mezglu A uz kaudzes un iestatiet tā STATUSS = 2 (gaidīšanas stāvoklis)

3. darbība: Atkārtojiet 4. un 5. darbību, līdz STACK ir tukšs

4. darbība: Atveriet augšējo mezglu N. Apstrādājiet to un iestatiet tā STATUSS = 3 (apstrādāts stāvoklis)

salīdziniet virknē

5. darbība: Uzspiediet uz kaudzītes visus N kaimiņus, kas ir gatavības stāvoklī (kuru STATUSS = 1) un iestatiet to STATUSS = 2 (gaidīšanas stāvoklis)

[CILPAS BEIGAS]

6. darbība: IZEJA

Pseidokods

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

DFS algoritma piemērs

Tagad, izmantojot piemēru, sapratīsim DFS algoritma darbību. Tālāk sniegtajā piemērā ir vērsts grafs ar 7 virsotnēm.

DFS algoritms

Tagad sāksim izpētīt grafiku, sākot no mezgla H.

1. darbība - Vispirms uzspiediet H uz kaudzes.

 STACK: H

2. darbība - POP augšējo elementu no kaudzes, t.i., H, un izdrukājiet to. Tagad IESPIEDIET visus H kaimiņus uz kaudzītes, kas ir gatavības stāvoklī.

 Print: H]STACK: A

3. darbība - POP augšējo elementu no kaudzes, t.i., A, un izdrukājiet to. Tagad IESPIEDIET visus A kaimiņus uz kaudzītes, kas ir gatavības stāvoklī.

 Print: A STACK: B, D

4. darbība - POP augšējo elementu no kaudzes, t.i., D, un izdrukājiet to. Tagad IESPIEDIET visus D kaimiņus uz kaudzītes, kas ir gatavības stāvoklī.

pavasara st 
 Print: D STACK: B, F

5. darbība - POP augšējo elementu no kaudzes, t.i., F, un izdrukājiet to. Tagad PUSH visus F kaimiņus uz kaudzīti, kas ir gatavības stāvoklī.

 Print: F STACK: B

6. darbība - POP augšējo elementu no kaudzes, t.i., B, un izdrukājiet to. Tagad IESPIEDIET visus B kaimiņus uz kaudzītes, kas ir gatavības stāvoklī.

 Print: B STACK: C

7. darbība - POP augšējo elementu no kaudzes, t.i., C, un izdrukājiet to. Tagad PUSH visus C kaimiņus uz kaudzīti, kas ir gatavības stāvoklī.

 Print: C STACK: E, G

8. darbība - POP augšējo elementu no steka, t.i., G un PUSH visus G kaimiņus uz kaudzīti, kas ir gatavības stāvoklī.

 Print: G STACK: E

9. darbība - POP augšējo elementu no kaudzes, t.i., E un PUSH visus E kaimiņus uz kaudzīti, kas ir gatavības stāvoklī.

 Print: E STACK:

Tagad visi grafika mezgli ir izstaigāti, un kaudze ir tukša.

Dziļuma pirmās meklēšanas algoritma sarežģītība

DFS algoritma laika sarežģītība ir O(V+E) , kur V ir virsotņu skaits un E ir grafa malu skaits.

DFS algoritma telpas sarežģītība ir O(V).

DFS algoritma ieviešana

Tagad apskatīsim DFS algoritma ieviešanu Java.

Šajā piemērā grafiks, ko mēs izmantojam, lai parādītu kodu, ir norādīts šādi:

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