djupetförsttraversering

Djupetförsttraversering, ofta förkortad DFS, är en metod för att systematiskt besöka noder i en graf eller ett träd. Den går så långt som möjligt längs varje gren innan den backar tillbaka till tidigare noder. DFS används för att hitta sammanhängande komponenter, lokalisera vägar eller möjliggöra andra algoritmer som topologisk sortering eller cykeldetektion. Den står i kontrast till bredden-först-traversering (BFS), som utförs i nivåer från startpunkten.

Algoritmen kan implementeras rekursivt eller iterativt. I den rekursiva versionen markeras startnoden som besökt, och för varje granne som inte har besökts anropas DFS rekursivt på grannen. I den iterativa versionen används en explicit stack: startnoden sätts på stacken, man poppar en nod, besöker den om den inte redan är det, och lägger dess ännu o besökta grannar på stacken. DFS fungerar både på riktade och of riktade grafer samt på träd.

Tid- och rymdkomplexitet: Tiden är O(V+E) i en graf med V noder och E kanter. Minnesbehoven är O(H) för rekursionens stackdjup, där H är grafens höjd, eller O(V) i värsta fall om man använder en explicit stack. DFS kan därför använda mycket minne i djupa grafer men är mycket snabb för att helt täcka en komponent.

Vanliga användningar inkluderar att hitta sammanhängande komponenter, utföra topologisk sortering, detektera cykler i riktade grafer samt generera pre- och postorderbesök i träd. Den används även inom problemlösning som labsituationer och pussel där fullständig genomgång av sökträdet krävs.