- Aktuell
- På stacken
- Färdiga
- Väg
Djupet-först-sökning (DFS)
Djupet-först-sökning utforskar en graf som någon som går genom en labyrint med ena handen på väggen: den följer en väg så långt det går, och går tillbaka först när det inte finns något nytt att gå till. Det gör den med en stack. Klicka på en nod för att börja där, välj ett mål om du vill, och stega genom sökningen för att se stacken växa och krympa, varje nod få sitt besöksnummer och kanterna som sluter en cykel. Tryck på Spela för att se sökningen, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst. Klicka på en nod för att göra den till start; byt klicket till Mål och klicka på en annan nod för att söka en väg dit. Talet på varje nod är i vilken ordning den besöktes, och raden under grafen är stacken, från starten upp till noden överst. Ny graf skapar en annan graf; välj hur många noder och kanter den har. När brädet är markerat stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.
Hur det fungerar
- Klicka på en nod för att göra den till start. Vill du söka en väg, byt klicket till Mål och klicka på en annan nod.
- Tryck på Spela, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst i sökningen.
- Följ stacken under grafen och besöksnumret på varje nod. Ny graf skapar en annan graf att prova.
Så fungerar djupet-först-sökning
Lägg startnoden på stacken. Upprepa sedan: titta på nästa granne till noden överst på stacken. En granne som inte har setts än får nästa besöksnummer, minns noden den nåddes från och läggs överst på stacken, så att sökningen fortsätter därifrån. När noden överst inte har några grannar kvar att kontrollera är den färdig och tas bort från stacken, och sökningen går tillbaka till noden under. När stacken är tom har varje nod som kan nås besökts.
Vad stacken berättar
Eftersom sökningen alltid fortsätter från den nyaste noden är stacken alltid en väg från starten till noden som undersöks. När målet nås är stacken en väg dit, men oftast inte den kortaste: den hittar bredden-först-sökning. I en graf utan riktningar sluter en kant till en nod som fortfarande ligger på stacken en cykel, utom när det är noden sökningen just kom från. De ihågkomna noderna bildar ett träd, djupet-först-trädet, och ordningen i vilken noderna blir färdiga är nyckeln till topologisk sortering.
Ofta ställda frågor
Vad är djupet-först-sökning?
Ett sätt att utforska en graf från en startnod genom att följa en väg så djupt det går, och gå tillbaka för att prova en annan gren först när det inte finns något nytt att gå till. Den använder en stack, eller rekursion, för att minnas vägen tillbaka.
Hittar djupet-först-sökning den kortaste vägen?
Nej. Den hittar en väg till målet om det finns en, men vägen kan vara mycket längre än nödvändigt, eftersom DFS håller fast vid den första grenen den provar. Använd bredden-först-sökning för minst antal kanter, eller Dijkstras algoritm när kanterna har längder.
Vad är skillnaden mellan DFS och BFS?
Djupet-först-sökning använder en stack och går djupt längs en väg innan den går tillbaka. Bredden-först-sökning använder en kö och sprider sig jämnt, ring för ring. Båda besöker varje nod som kan nås på en tid som växer med antalet noder plus kanter; BFS hittar kortaste vägar, medan DFS är det naturliga valet för cykler, labyrinter och topologisk sortering.
Hur hittar DFS en cykel?
Om sökningen i en graf utan riktningar möter en kant till en nod som fortfarande ligger på stacken, och den noden inte är den den just kom från, så sluter kanten en slinga. I appen säger statusraden det när det händer.
Skickas min graf någonstans?
Nej. Grafen skapas och genomsöks i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor