Dybde først Søk eller Dybde første traversal er en rekursiv algoritme for å søke etter alle noder i en graf eller treet data struktur. Traversal betyr å besøke alle nodene i en graf.

Dybde Først Søk Algoritme

En standard DFS gjennomføring setter hver toppunktet på grafen i en av to kategorier:

1. Besøkte
2. Ikke Besøkt

hensikten med algoritmen er å merke hver toppunktet som besøkte samtidig unngå sykluser.,

DFS-algoritmen fungerer som følger:

1. Start ved å sette en av grafen er hjørnene på toppen av en stabel.
2. Ta det øverste elementet i bunken og legge den til den besøkte listen.
3. Opprette en liste av at toppunktet er tilstøtende noder. Legg til de som ikke er med i besøkte listen til toppen av bunken.
4. Hold gjenta trinnene 2 og 3 til bunken er tom.

Dybde Første Eksempel på Søk

La oss se hvordan Dybde Først Søk algoritmen fungerer med et eksempel. Vi bruker en undirected graf med 5 noder.,

Vi starter fra vertex-0, DFS-algoritmen starter ved å sette den i Besøkte liste og setter alle sine tilstøtende noder i bunken.

Neste, vi besøker element på toppen av stabelen dvs. 1 og gå til tilstøtende noder. Siden 0 har allerede blitt besøkt, vi besøk 2 i stedet.,

Vertex 2 har en ubenyttede ved siden toppunktet i 4, så vi legger det til toppen av bunken og besøke den.

Når vi besøker det siste elementet 3, det har ikke noe ubenyttede tilstøtende noder, så vi har gjennomført Dybde Første Traversal av grafen.,

DFS Pseudocode (rekursiv implementering)

pseudocode for DFS er vist nedenfor. I init () – funksjonen, legg merke til at vi kjører DFS-funksjonen på hver node. Dette er fordi grafen kan ha to forskjellige frakoblet deler så å sørge for at vi dekker hver toppunktet, kan vi også kjøre DFS-algoritme 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 Dybde-Først Søk Algoritme med et eksempel er vist nedenfor. Koden har blitt forenklet, slik at vi kan fokusere på algoritmen snarere enn andre detaljer.

Kompleksitet og Dybde Først Søk

Den tid kompleksiteten i DFS-algoritmen er representert i form av O(V + E), der V er antall noder og E er nummeret på kantene.

plassen kompleksiteten til algoritmen er O(V).,

Anvendelse av DFS Algoritme

1. For å finne veien
2. for Å teste hvis grafen er bipartite
3. For å finne den sterkt koblet komponentene i en graf
4. For å oppdage sykluser i en graf