- Aktuel
- På stakken
- Færdig
- Vej
Dybde-først-søgning (DFS)
Dybde-først-søgning udforsker en graf som en, der går gennem en labyrint med én hånd på væggen: den følger én vej så langt, den kan, og går først tilbage, når der ikke er noget nyt at gå til. Det gør den med en stak. Klik på en knude for at starte fra den, vælg et mål, hvis du vil, og gå trin for trin gennem søgningen for at se stakken vokse og skrumpe, hver knude få sit besøgsnummer og de kanter, der lukker en kreds. Tryk på Afspil for at se søgningen, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst. Klik på en knude for at gøre den til start; skift klikket til Mål, og klik på en anden knude for at søge efter en vej dertil. Tallet på hver knude er den rækkefølge, den blev besøgt i, og rækken under grafen er stakken, fra starten op til knuden øverst. Ny graf laver en anden graf; vælg, hvor mange knuder og kanter den har. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End springer til starten og slutningen.
Sådan virker det
- Klik på en knude for at gøre den til start. Vil du søge efter en vej, så skift klikket til Mål, og klik på en anden knude.
- Tryk på Afspil, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst i søgningen.
- Følg stakken under grafen og besøgsnummeret på hver knude. Ny graf laver en anden graf, du kan prøve.
Sådan virker dybde-først-søgning
Læg startknuden på stakken. Gentag så: se på den næste nabo til knuden øverst på stakken. En nabo, der ikke er set endnu, får det næste besøgsnummer, husker den knude, den blev nået fra, og lægges øverst på stakken, så søgningen fortsætter derfra. Når knuden øverst ikke har flere naboer at undersøge, er den færdig og tages af stakken, og søgningen går tilbage til knuden nedenunder. Når stakken er tom, er hver knude, der kan nås, besøgt.
Hvad stakken fortæller dig
Fordi søgningen altid fortsætter fra den nyeste knude, er stakken altid en vej fra starten til den knude, der ses på. Når målet nås, er stakken en vej dertil, men som regel ikke den korteste: den finder bredde-først-søgning. I en graf uden retninger lukker en kant til en knude, der stadig er på stakken, en kreds, medmindre det er den knude, søgningen lige kom fra. De huskede knuder danner et træ, dybde-først-træet, og den rækkefølge, knuderne bliver færdige i, er nøglen til topologisk sortering.
Ofte stillede spørgsmål
Hvad er dybde-først-søgning?
En måde at udforske en graf fra en startknude ved at følge én vej så dybt, den går, og først gå tilbage for at prøve en anden gren, når der ikke er noget nyt at gå til. Den bruger en stak eller rekursion til at huske vejen tilbage.
Finder dybde-først-søgning den korteste vej?
Nej. Den finder en vej til målet, hvis der er en, men den vej kan være meget længere end nødvendigt, fordi DFS holder fast i den første gren, den prøver. Brug bredde-først-søgning for færrest kanter eller Dijkstras algoritme, når kanterne har længder.
Hvad er forskellen på DFS og BFS?
Dybde-først-søgning bruger en stak og går dybt ad én vej, før den går tilbage. Bredde-først-søgning bruger en kø og breder sig jævnt ud, ring for ring. Begge besøger hver knude, der kan nås, i en tid, der vokser med antallet af knuder plus kanter; BFS finder korteste veje, mens DFS er det naturlige valg til kredse, labyrinter og topologisk sortering.
Hvordan finder DFS en kreds?
Hvis søgningen i en graf uden retninger møder en kant til en knude, der stadig er på stakken, og den knude ikke er den, den lige kom fra, så lukker kanten en løkke. I appen siger statuslinjen det, når det sker.
Bliver min graf sendt nogen steder hen?
Nej. Grafen laves og gennemsøges i din browser, og dine seneste indstillinger gemmes i denne browsers lokale lager.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor