Dybde-først-søgning (DFS)
Gå ind i en labyrint, fortsæt, til du rammer en blindgyde, gå så tilbage til den sidste forgrening, og prøv den næste vej. Sådan udforsker dybde-først-søgning en graf. Den er en af de enkleste grafalgoritmer, og stakken, den holder, fortæller mere, end man skulle tro.
Idéen
En graf er en mængde knuder forbundet af kanter: rum og døre, websider og links, opgaver og de opgaver, de afhænger af. Dybde-først-søgning besøger hver knude, den kan nå fra en start, men i en bestemt rækkefølge: den fortsætter altid fra den knude, den senest nåede. Den holder en stak af de knuder, den er inde i. En ny knude lægges øverst, og en knude tages først af, når alt omkring den er udforsket.
Trin for trin
Læg starten på stakken, og giv den besøgsnummer 1. Se på den næste nabo til knuden øverst. Hvis den ikke er set, så giv den det næste besøgsnummer, husk den knude, den blev nået fra, og læg den øverst på stakken. Hvis den er set før, så spring den over. Når knuden øverst ikke har flere naboer at undersøge, er den færdig: tag den af, og fortsæt med knuden nedenunder. Stop, når stakken er tom, eller når målet er nået.
Et eksempel
Tag en graf med kanterne A–B, A–C, B–D, C–D, C–E og D–F, start ved A, og undersøg naboer i alfabetisk rækkefølge. Fra A går søgningen til B, fra B til D, fra D til C og fra C til E, så stakken er A, B, D, C, E. Undervejs ser C knuden A, som stadig er på stakken: kanten C–A lukker kredsen A, B, D, C. E har intet nyt, så den er færdig, derefter C, og søgningen går tilbage til D, som stadig har F. Besøgsrækkefølgen er A, B, D, C, E, F. Med E som mål stopper DFS med vejen A → B → D → C → E, fire kanter, selvom A → C → E kun tager to.
Hvad den er god til
Stakken er altid en vej fra starten til den aktuelle knude, og det gør DFS naturlig til labyrinter og gåder: det er idéen bag backtracking. I en graf uden retninger lukker en kant til en knude, der stadig er på stakken, en kreds. I en graf med retninger får man en topologisk rækkefølge ved at liste knuderne i omvendt rækkefølge af, hvornår de bliver færdige, så opgaver kommer efter de opgaver, de afhænger af. Dybde-først-søgning finder også sammenhængende komponenter, broer og artikulationspunkter, og dens tilfældige udgave er en klassisk måde at lave labyrinter på.
Historie
I 1800-tallet beskrev den franske matematiker Charles Pierre Trémaux en måde at slippe ud af enhver labyrint ved at markere gangene, hvilket er dybde-først-søgning med kridt. I 1972 og 1973 viste Robert Tarjan og John Hopcroft, at DFS løser mange grafproblemer i lineær tid, fra stærkt sammenhængende komponenter til at afgøre, om en graf kan tegnes uden krydsninger. De fik Turingprisen i 1986, blandt andet for det arbejde.
Udforsk den
Åbn appen, og tryk på Trin. Knuden, hvis naboer undersøges, er fremhævet, knuder på stakken er blå, og færdige knuder er grønne, hver med sit besøgsnummer. Stakken vises under grafen, fra starten til knuden øverst. Hold øje med statuslinjen for de kanter, der lukker en kreds, og vælg et mål for at se, hvor lang den fundne vej kan være sammenlignet med bredde-først-søgning.
Ofte stillede spørgsmål
Hvad er tidskompleksiteten for DFS?
O(V + E) for V knuder (vertices) og E kanter: hver knude lægges på og tages af stakken én gang, og hver kant undersøges fra begge ender. Den kræver O(V) ekstra hukommelse til stakken og markeringerne.
Hvorfor bruger DFS en stak?
Fordi sidst ind, først ud får søgningen til at fortsætte fra den nyeste knude og gå tilbage til den før. Rekursion gør det samme med programmets kaldstak. Med en kø i stedet ville søgningen brede sig ring for ring: det er bredde-først-søgning.
Er rekursiv DFS et problem for store grafer?
Det kan den være: en lang vej betyder dyb rekursion, og mange sprog begrænser, hvor dybt kald kan gå. En eksplicit stak i en løkke undgår den grænse og besøger knuderne i samme rækkefølge.
Hvor bruges DFS?
Til at løse labyrinter og gåder med backtracking, finde kredse, ordne opgaver efter deres afhængigheder (topologisk sortering), finde sammenhængende og stærkt sammenhængende komponenter, lave labyrinter og i compilere og byggeværktøjer, der gennemgår afhængighedsgrafer.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv dybde-først-søgning