dybde første søgning eller dybde første traversal er en rekursiv algoritme til søgning i alle hjørner af en graf eller trædatastruktur. Traversal betyder at besøge alle knudepunkter i en graf.

Dybde-Først-Søgning Algoritmen

En standard DFS gennemførelse sætter hvert hjørne af grafen i en af to kategorier:

1. Besøgte
2. Ikke Besøgt

formålet med algoritmen er at markere hver vertex, som besøgte samtidig undgå cykler.,

DFS-algoritmen fungerer som følger:

1. Start med at placere en af grafens hjørner oven på en stak.
2. tag det øverste element i stakken og tilføj det til den besøgte liste.
3. Opret en liste over det Verte.tilstødende noder. Tilføj dem, der ikke er i den besøgte liste til toppen af stakken.
4. fortsæt med at gentage trin 2 og 3, indtil stakken er tom.

dybde første Søgeeksempel

lad os se, hvordan dybden første søgealgoritme fungerer med et eksempel. Vi bruger en undirected graf med 5 hjørner.,

Vi starter fra isse 0, DFS algoritmen starter med at sætte det i de Besøgte listen og lægge alle sine tilstødende vertices i stakken.

Næste, vi besøg af et element på toppen af stakken, dvs 1 og gå til sin tilstødende knuder. Da 0 allerede er besøgt, besøger vi 2 i stedet.,

Vertex 2 har et ubesøgt tilstødende vertex 4, så vi kan tilføje, at til toppen af stakken og besøge det.

efter at vi har besøgt det sidste element 3, har det ikke nogen ubesøgte tilstødende noder, så vi har afsluttet dybden første krydsning af grafen.,

DFS pseudokode (rekursiv implementering)

pseudokoden for DFS er vist nedenfor. I init () – funktionen skal du bemærke, at vi kører DFS-funktionen på hver node. Dette skyldes, at grafen muligvis har to forskellige frakoblede dele, så for at sikre, at vi dækker hvert hjørne, kan vi også køre DFS-algoritmen på hver node.,

DFS(G, u) u.visited = true for each v ∈ G.Adj if v.visited == false DFS(G,v) init() { For each u ∈ G u.visited = false For each u ∈ G DFS(G, u)}

DFS implementering i Python, Java og C/C++

koden for dybden første søgealgoritme med et eksempel er vist nedenfor. Koden er blevet forenklet, så vi kan fokusere på algoritmen snarere end andre detaljer.

Kompleksiteten af Dybde Først Søgning

Den tid, kompleksitet af DFS algoritme er repræsenteret i form af O(V + E), hvor V er antallet af knuder og E er antallet af kanter.

algoritmens rumkompleksitet er O(V).,

Anvendelse af DFS Algoritme

1. For at finde den sti
2. til At teste, hvis graf er todelt
3. For at finde den stærkt forbundet komponenter af en graf
4. For at opdage-cykler i en graf