Djupet först-sökning (DFS)
Utforskar en graf genom att följa en väg så djupt det går och sedan gå tillbaka till senaste förgrening. Stacken på skärmen är den vägen.
- tid O(V + E)
- minne O(V)
- använder en stack
Vad betyder det här?
- Nod: en punkt i grafen, här ritad som en cirkel med en bokstav.
- Kant: en linje som förbinder två noder. Här kan man gå längs den åt båda hållen.
- Grannar: de noder som är förbundna med en nod genom en kant. De granskas i bokstavsordning.
- Kö: först in, först ut. BFS tar alltid den nod som har väntat längst.
- Stack: sist in, först ut. DFS fortsätter alltid från den nod den nådde sist.
- V och E: antalet noder (vertices) och kanter (edges). O(V + E) betyder att varje nod och varje kant hanteras ett fast antal gånger.
- på stacken
- aktuell
- klar
- kant i sökträdet
- överhoppad kant
Börja i A. Tryck på Spela upp eller stega igenom sökningen.
Blanksteg: spela upp eller pausa. Vänster och höger pil: steg. Home och End: hoppa.
Prova det här: Välj grafen med cykler. Varje streckad kant leder tillbaka till en nod som redan ligger på stacken eller är klar: den kanten sluter en cykel.
Så fungerar det
DFS anropar sig själv för den första granne den inte har sett än, sedan för den grannens första nya granne, och så vidare. När en nod inte har några nya grannar kvar avslutas dess anrop, och DFS går ett steg tillbaka för att pröva nästa granne där. De öppna anropen bildar en stack, som alltid är vägen från start till den aktuella noden. Talet bredvid en nod visar i vilken ordning den besöktes.
När det är ett bra val
Använd DFS för att ta reda på vad som alls går att nå, för att hitta cykler, för att gå igenom en labyrint eller för att ordna uppgifter som beror på varandra. Den hittar inte den kortaste vägen.