Šiame straipsnyje aptarsime DFS algoritmą duomenų struktūroje. Tai rekursinis algoritmas, skirtas ieškoti visose medžio duomenų struktūros ar grafiko viršūnėse. Pirmojo gylio paieškos (DFS) algoritmas pradedamas nuo pradinio grafiko G mazgo ir eina gilyn, kol randame tikslo mazgą arba mazgą be vaikų.
Dėl rekursyvaus pobūdžio DFS algoritmui įgyvendinti galima naudoti kamino duomenų struktūrą. DFS diegimo procesas yra panašus į BFS algoritmą.
Žingsnis po žingsnio DFS perėjimo įgyvendinimo procesas pateikiamas taip:
- Pirmiausia sukurkite krūvą su visu grafiko viršūnių skaičiumi.
- Dabar pasirinkite bet kurią viršūnę kaip pradžios tašką ir įstumkite tą viršūnę į krūvą.
- Po to stumkite nelankytą viršūnę (greta viršūnės krūvos viršuje) į krūvos viršūnę.
- Dabar kartokite 3 ir 4 veiksmus, kol nebeliks jokių viršūnių, kurias būtų galima aplankyti iš krūvos viršuje esančios viršūnės.
- Jei viršūnės neliko, grįžkite atgal ir iškelkite viršūnę iš krūvos.
- Kartokite 2, 3 ir 4 veiksmus, kol krūva bus tuščia.
DFS algoritmo taikymas
DFS algoritmo naudojimo programos pateikiamos taip:
- DFS algoritmas gali būti naudojamas topologiniam rūšiavimui įgyvendinti.
- Jis gali būti naudojamas ieškant kelių tarp dviejų viršūnių.
- Jis taip pat gali būti naudojamas aptikti ciklus grafike.
- DFS algoritmas taip pat naudojamas vieno sprendimo galvosūkiams.
- DFS naudojamas nustatyti, ar grafikas yra dvišalis, ar ne.
Algoritmas
1 žingsnis: NUSTATYTI STATUSĄ = 1 (parengties būsena) kiekvienam G mazgui
2 žingsnis: Pastumkite pradinį mazgą A ant krūvos ir nustatykite jo STATUS = 2 (laukimo būsena)
3 veiksmas: Kartokite 4 ir 5 veiksmus, kol STACK bus tuščias
4 veiksmas: Atidarykite viršutinį mazgą N. Apdorokite jį ir nustatykite jo STATUS = 3 (apdorota būsena)
5 veiksmas: Įstumkite į krūvą visus N kaimynus, kurie yra parengties būsenoje (kurių STATUSAS = 1) ir nustatykite jų STATUSAS = 2 (laukimo būsena)
[KILPOS PABAIGA]
6 veiksmas: IŠĖJIMAS
Pseudokodas
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 algoritmo pavyzdys
Dabar, naudodami pavyzdį, supraskime, kaip veikia DFS algoritmas. Toliau pateiktame pavyzdyje yra nukreiptas grafikas, turintis 7 viršūnes.
Dabar pradėkime nagrinėti grafiką, pradedant nuo mazgo H.
1 žingsnis - Pirmiausia stumkite H ant kamino.
STACK: H
2 žingsnis - Iškelkite viršutinį elementą iš krūvos, t. y. H, ir atsispausdinkite. Dabar įstumkite visus H kaimynus į krūvą, kurie yra paruoštos būsenos.
10 iš 50
Print: H]STACK: A
3 veiksmas - Iškelkite viršutinį elementą iš krūvos, t. y. A, ir atsispausdinkite. Dabar įstumkite visus A kaimynus į krūvą, kurie yra parengtos būsenos.
Print: A STACK: B, D
4 veiksmas - Iškelkite viršutinį elementą iš krūvos, t. y. D, ir atsispausdinkite. Dabar įstumkite visus D kaimynus į krūvą, kurie yra paruoštos būsenos.
Print: D STACK: B, F
5 veiksmas - Iškelkite viršutinį elementą iš krūvos, t. y. F, ir atsispausdinkite. Dabar įstumkite visus F kaimynus į krūvą, kurie yra parengties būsenoje.
Print: F STACK: B
6 veiksmas - Iškelkite viršutinį elementą iš krūvos, t. y. B, ir atsispausdinkite. Dabar įstumkite visus B kaimynus į krūvą, kurie yra parengtos būsenos.
Print: B STACK: C
7 veiksmas - Iškelkite viršutinį elementą iš krūvos, t. y. C, ir atsispausdinkite. Dabar įstumkite visus C kaimynus į krūvą, kurie yra parengties būsenoje.
Print: C STACK: E, G
8 veiksmas - Iškelkite viršutinį elementą iš krūvos, t. y. G, ir stumkite visus G gretimus į krūvą, kurie yra parengtos būsenos.
Print: G STACK: E
9 veiksmas - POP viršutinį elementą iš krūvos, t. y. E, ir stumkite visus E kaimyninius į krūvą, kurie yra parengties būsenos.
Print: E STACK:
Dabar visi grafiko mazgai buvo pereiti, o krūva tuščia.
Pirmojo gylio paieškos algoritmo sudėtingumas
DFS algoritmo laiko sudėtingumas yra O (V+E) , kur V – viršūnių skaičius, o E – kraštinių skaičius grafe.
DFS algoritmo erdvės sudėtingumas yra O(V).
DFS algoritmo įgyvendinimas
Dabar pažiūrėkime, kaip įdiegtas DFS algoritmas Java.
Šiame pavyzdyje grafikas, kurį naudojame kodui parodyti, pateikiamas taip:
/*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;>