Djupet-först-sökning (DFS)

Gå in i en labyrint, fortsätt tills du når en återvändsgränd, gå sedan tillbaka till den senaste förgreningen och prova nästa väg. Så utforskar djupet-först-sökning en graf. Det är en av de enklaste grafalgoritmerna, och stacken den håller berättar mer än man kanske tror.

En graf med en lång kedja av noder från starten markerad i gult, färdiga noder i ljuslila och stacken ritad som en rad rutor under
En graf med en lång kedja av noder från starten markerad i gult, färdiga noder i ljuslila och stacken ritad som en rad rutor under

Idén

En graf är en mängd noder sammanbundna av kanter: rum och dörrar, webbsidor och länkar, uppgifter och de uppgifter de beror på. Djupet-först-sökning besöker varje nod den kan nå från en start, men i en viss ordning: den fortsätter alltid från den nod den nådde senast. Den håller en stack med noderna den är inne i. En ny nod läggs överst, och en nod tas bort först när allt runt den är utforskat.

Steg för steg

Lägg starten på stacken och ge den besöksnummer 1. Titta på nästa granne till noden överst. Om den inte har setts, ge den nästa besöksnummer, minns noden den nåddes från och lägg den överst på stacken. Om den har setts förut, hoppa över den. När noden överst inte har några grannar kvar att kontrollera är den färdig: ta bort den och fortsätt med noden under. Sluta när stacken är tom, eller när målet är nått.

Ett exempel

Ta en graf med kanterna A–B, A–C, B–D, C–D, C–E och D–F, börja i A och kontrollera grannar i alfabetisk ordning. Från A går sökningen till B, från B till D, från D till C och från C till E, så stacken är A, B, D, C, E. På vägen ser C noden A, som fortfarande ligger på stacken: kanten C–A sluter cykeln A, B, D, C. E har inget nytt, så den är färdig, sedan C, och sökningen går tillbaka till D, som fortfarande har F. Besöksordningen är A, B, D, C, E, F. Med E som mål stannar DFS med vägen A → B → D → C → E, fyra kanter, fast A → C → E bara tar två.

Vad den är bra för

Stacken är alltid en väg från starten till den aktuella noden, vilket gör DFS naturlig för labyrinter och pussel: det är idén bakom backtracking. I en graf utan riktningar sluter en kant till en nod som fortfarande ligger på stacken en cykel. I en graf med riktningar ger en lista av noderna i omvänd ordning mot när de blir färdiga en topologisk ordning, så att uppgifter kommer efter de uppgifter de beror på. Djupet-först-sökning hittar också sammanhängande komponenter, broar och artikulationspunkter, och dess slumpmässiga variant är ett klassiskt sätt att skapa labyrinter.

Historia

På 1800-talet beskrev den franske matematikern Charles Pierre Trémaux ett sätt att ta sig ut ur vilken labyrint som helst genom att markera gångarna, vilket är djupet-först-sökning med krita. 1972 och 1973 visade Robert Tarjan och John Hopcroft att DFS löser många grafproblem i linjär tid, från starkt sammanhängande komponenter till att avgöra om en graf kan ritas utan korsningar. De fick Turingpriset 1986, delvis för det arbetet.

Robert Tarjan, som 1972–73 tillsammans med John Hopcroft visade att djupet-först-sökning löser många grafproblem i linjär tid; de fick Turingpriset 1986 delvis för det arbetet.
Robert Tarjan, som 1972–73 tillsammans med John Hopcroft visade att djupet-först-sökning löser många grafproblem i linjär tid; de fick Turingpriset 1986 delvis för det arbetet.

Utforska den

Öppna appen och tryck på Steg. Noden vars grannar kontrolleras är markerad, noder på stacken är blå och färdiga noder är gröna, var och en med sitt besöksnummer. Stacken visas under grafen, från starten till noden överst. Håll ögonen på statusraden för kanterna som sluter en cykel, och välj ett mål för att se hur lång den funna vägen kan bli jämfört med bredden-först-sökning.

Ofta ställda frågor

Vad är tidskomplexiteten för DFS?

O(V + E) för V noder (hörn) och E kanter: varje nod läggs på och tas bort från stacken en gång, och varje kant undersöks från båda ändarna. Den behöver O(V) extra minne för stacken och markeringarna.

Varför använder DFS en stack?

Därför att sist in, först ut får sökningen att fortsätta från den nyaste noden och gå tillbaka till den före. Rekursion gör samma sak med programmets anropsstack. Med en kö i stället skulle sökningen sprida sig ring för ring: det är bredden-först-sökning.

Är rekursiv DFS ett problem för stora grafer?

Det kan den vara: en lång väg innebär djup rekursion, och många språk begränsar hur djupt anrop kan gå. En explicit stack i en loop undviker den gränsen och besöker noderna i samma ordning.

Var används DFS?

För att lösa labyrinter och pussel med backtracking, hitta cykler, ordna uppgifter efter deras beroenden (topologisk sortering), hitta sammanhängande och starkt sammanhängande komponenter, skapa labyrinter, och i kompilatorer och byggverktyg som går igenom beroendegrafer.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Prova djupet-först-sökning