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.
- O(V + E)
- minne O(V)
- stack
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.
Stack: sist in, först ut. DFS fortsätter alltid från den nod den nådde sist.
Fler begrepp på sidan
- 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.
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.