algorithm
Djup första sökning

Introduktion till djup-första sökning

Djup-först-sökning är en algoritm för att korsa eller söka i träd- eller diagramdatastrukturer. Man börjar vid roten och utforskar så långt som möjligt längs varje gren innan backtracking. En version av den första djup-sökningen undersöktes på 1800-talets franska matematiker Charles Pierre Trémaux som en strategi för att lösa labyrinter.

Djup-först-sökning är ett systematiskt sätt att hitta alla vertikaler som kan nås från en källvinkel. Liksom bredd-första sökning, DFS korsar en ansluten komponent i en given graf och definierar ett spännande träd. Grundidén med djup-först-sökning är metodiskt att utforska varje kant. Vi börjar om från olika hörn efter behov. Så snart vi upptäcker ett toppunkt börjar DFS utforska från det (till skillnad från BFS, som sätter ett toppunkt i en kö så att det utforskar det senare).

Låt oss titta på ett exempel. Vi går igenom denna graf:

Vi går igenom diagrammet enligt dessa regler:

• Vi börjar från källan.
• Ingen nod kommer att besökas två gånger.
• De noder vi inte besöker ännu, kommer att färgas vita.
• Noden vi besökte, men inte besökte alla sina barnnoder, kommer att färgas grå.
• Helt korsade noder kommer att färgas svart.

Låt oss titta på det steg för steg:

Vi kan se ett viktigt nyckelord. Det är backedge . Du kan se. 5-1 kallas backedge. Det beror på att vi ännu inte är klara med node-1 , så att gå från en annan nod till nod-1 betyder att det finns en cykel i diagrammet. Om vi kan gå från en grå nod till en annan i DFS, kan vi vara säkra på att grafen har en cykel. Detta är ett av sätten att upptäcka cykel i en graf. Beroende på källnod och ordningen av noderna vi besöker, kan vi ta reda på någon kant i en cykel som backedge. Till exempel: om vi gick till 5 från 1 först, skulle vi ha upptäckt 2-1 som backedge.

Kanten som vi tar för att gå från grå nod till vit nod kallas trädkant . Om vi håller bara trädet kanten s och ta bort andra, får vi DFS träd.

Om vi kan besöka en redan besökt nod i ett riktat diagram , måste det vara en backedge . Men för riktade diagram måste vi kontrollera färgerna. Om och bara om vi kan gå från en grå nod till en annan grå nod kallas det en backedge .

I DFS kan vi också hålla tidsstämplar för varje nod, som kan användas på många sätt (t.ex.: Topological Sort).

1. När en nod v ändras från vit till grå registreras tiden i d [v] .
2. När en nod v ändras från grå till svart registreras tiden i f [v] .

Här betyder d [] upptäckt tid och f [] betyder avslutningstid . Vår pesudokod kommer att se ut:

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

Komplexitet:

Varje nod och kanter besöks en gång. Så komplexiteten för DFS är O (V + E) , där V anger antalet noder och E anger antalet kanter.

Applications of Deepth First Search:

• Hitta alla parets kortaste sökvägen i en riktad graf.
• Upptäck cykel i en graf.
• Sökväg.
• Topologisk sortering.
• Testa om en graf är tvåparti.
• Hitta starkt anslutna komponenter.
• Lösa pussel med en lösning.