Depth first Search of depth first traversal is een recursief algoritme voor het doorzoeken van alle hoekpunten van een grafiek of boomgegevensstructuur. Traversal betekent het bezoeken van alle knooppunten van een grafiek.

diepte eerste zoekalgoritme

een standaard DFS-implementatie plaatst elk hoekpunt van de grafiek in een van twee categorieën:

1. bezocht
2. niet bezocht

het doel van het algoritme is om elk hoekpunt als bezocht te markeren terwijl cycli worden vermeden.,

het DFS-algoritme werkt als volgt:

1. begin met een van de hoekpunten van de grafiek op een stapel te plaatsen.
2. neem het bovenste item van de stack en voeg het toe aan de bezochte lijst.
3. Maak een lijst van de aangrenzende knooppunten van dat vertex. Voeg degenen die niet in de bezochte lijst staan toe aan de top van de stack.
4. herhaal stap 2 en 3 totdat de stack leeg is.

Depth First Search Voorbeeld

laten we eens kijken hoe het Depth First Search algoritme werkt met een voorbeeld. We gebruiken een niet-gerichte grafiek met 5 hoekpunten.,

we beginnen met vertex 0, het DFS-algoritme begint door het in de bezochte lijst te plaatsen en alle aangrenzende hoekpunten in de stack te plaatsen.

vervolgens bezoeken we het element aan de bovenkant van de stapel, d.w.z. 1 en gaan naar de aangrenzende nodes. Aangezien 0 al bezocht is, bezoeken we er 2 in plaats daarvan.,

Vertex 2 is een niet-aangrenzende vertex 4, zodat we die toevoegen aan de bovenkant van de stapel en het te bezoeken.

nadat we het laatste element 3 hebben bezocht, heeft het geen niet bezochte aangrenzende knooppunten, dus hebben we de diepte eerste Traversal van de grafiek voltooid.,

DFS Pseudocode (recursieve implementatie)

De pseudocode voor DFS wordt hieronder weergegeven. In de functie init (), merk op dat we de DFS-functie op elk knooppunt uitvoeren. Dit komt omdat de grafiek twee verschillende losgekoppelde delen kan hebben dus om ervoor te zorgen dat we elk hoekpunt behandelen, kunnen we ook het DFS-algoritme op elk knooppunt uitvoeren.,

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 implementatie in Python, Java en C/c++

de code voor het Depth First Search algoritme met een voorbeeld wordt hieronder getoond. De code is vereenvoudigd zodat we ons kunnen concentreren op het algoritme in plaats van andere details.

complexiteit van de diepte Eerste zoekopdracht

De tijdscomplexiteit van het DFS-algoritme wordt weergegeven in de vorm vanO(V + E), waarbijV het aantal knooppunten is enE het aantal randen is.

De ruimtecomplexiteit van het algoritme is O(V).,

toepassing van DFS-algoritme

1. Voor het vinden van het pad
2. om te testen of de grafiek bipartiet is
3. voor het vinden van de sterk verbonden componenten van een grafiek
4. Voor het detecteren van cycli in een grafiek