algorithm
Diepte eerste zoekopdracht

Inleiding tot diepte-eerste zoekopdracht

Diepte-eerst zoeken is een algoritme voor het doorkruisen of doorzoeken van boom- of grafiekdatastructuren. Je begint bij de wortel en onderzoekt zo ver mogelijk langs elke tak voordat je terugkeert. Een versie van diepte-eerste zoekopdracht werd onderzocht in de 19e-eeuwse Franse wiskundige Charles Pierre Trémaux als een strategie voor het oplossen van doolhoven.

Diepte-eerst zoeken is een systematische manier om alle hoekpunten te vinden die bereikbaar zijn vanaf een bronpunt. Net als breedte-eerst zoeken, doorkruist DFS een verbonden component van een gegeven grafiek en definieert een overspannende boom. Het basisidee van diepte-eerste zoeken is methodisch elke rand verkennen. We beginnen opnieuw vanuit verschillende hoekpunten als dat nodig is. Zodra we een hoekpunt ontdekken, begint DFS met het verkennen ervan (in tegenstelling tot BFS, dat een hoekpunt in een wachtrij plaatst zodat het er later uit onderzoekt).

Laten we een voorbeeld bekijken. We zullen deze grafiek doorlopen:

We zullen de grafiek volgen volgens deze regels:

• We beginnen bij de bron.
• Geen enkel knooppunt zal twee keer worden bezocht.
• De knooppunten die we nog niet hebben bezocht, worden wit gekleurd.
• Het knooppunt dat we hebben bezocht, maar niet alle onderliggende knooppunten heeft bezocht, wordt grijs gekleurd.
• Volledig doorkruiste knooppunten worden zwart gekleurd.

Laten we het stap voor stap bekijken:

We kunnen één belangrijk trefwoord zien. Dat is een achteruitgang . Je kan zien. 5-1 wordt backedge genoemd. Dit komt omdat we nog niet klaar zijn met knooppunt-1 , dus van een ander knooppunt naar knooppunt 1 gaan betekent dat er een cyclus in de grafiek is. Als we in DFS van de ene grijze knoop naar de andere kunnen gaan, weten we zeker dat de grafiek een cyclus heeft. Dit is een van de manieren om de cyclus in een grafiek te detecteren. Afhankelijk van de bron knooppunt en de volgorde van de knooppunten die we bezoeken, kunnen we vinden elke rand in een cyclus als backedge. Bijvoorbeeld: als we eerst naar 5 van 1 gingen, zouden we 2-1 als backedge hebben ontdekt.

De rand die we nemen om van grijze knoop naar witte knoop te gaan, wordt boomrand genoemd . Als we alleen de boomranden behouden en anderen verwijderen, krijgen we een DFS-boom .

Als we in een niet-geleide grafiek een reeds bezocht knooppunt kunnen bezoeken, moet dat een backedge zijn . Maar voor gerichte grafieken moeten we de kleuren controleren. Als en alleen als we van de ene grijze knoop naar een andere grijze knoop kunnen gaan, wordt dat een backedge genoemd .

In DFS kunnen we ook tijdstempels houden voor elk knooppunt, die op vele manieren kunnen worden gebruikt (bijvoorbeeld: Topologische sortering).

1. Wanneer een knooppunt v wordt veranderd van wit naar grijs, wordt de tijd vastgelegd in d [v] .
2. Wanneer een knooppunt v wordt gewijzigd van grijs in zwart, wordt de tijd vastgelegd in f [v] .

Hier betekent d [] ontdekkingstijd en f [] betekent eindtijd . Onze pesudo-code ziet eruit als:

Procedure DFS(G):
for each node u in V[G]
    color[u] := white
    parent[u] := NULL
end for
time := 0
for each node u in V[G]
    if color[u] == white
        DFS-Visit(u)
    end if
end for

Procedure DFS-Visit(u):
color[u] := gray
time := time + 1
d[u] := time
for each node v adjacent to u
    if color[v] == white
        parent[v] := u
        DFS-Visit(v)
    end if
end for
color[u] := black
time := time + 1
f[u] := time

complexiteit:

Elke knooppunten en randen worden één keer bezocht. Dus de complexiteit van DFS is O (V + E) , waarbij V het aantal knopen aangeeft en E het aantal randen.

Toepassingen van Depth First Search:

• Zoeken naar het kortste pad van alle paren in een ongerichte grafiek.
• Detecteren cyclus in een grafiek.
• Padvinden.
• Topologische sortering.
• Testen of een grafiek tweedelig is.
• Sterk verbonden component vinden.
• Puzzels oplossen met één oplossing.