Module 5 Graph Search 20

DFS — Depth-First Search (Stack + Backtracking + DFS Tree)

DFS explores as deep as possible before backtracking. Internally it behaves like a stack (or recursion). Click a node to set source.

V 6  ·  E 7 Source 0 Step 0
Legend: orange = current node (top of stack), purple = discovered (in stack), green = finished (popped). Blue/orange edge = the neighbor being checked. When a node has no more unvisited neighbors, DFS backtracks.
Stack bottom → top
Traversal depth-first + backtracking Time O(V + E) 

        


        

          When DFS discovers v from u, we set parent[v] = u. These parent pointers form the DFS tree.
        


        

          

        


        

          

          
        

      

    


    

      

        Next: 21 — Applications of DFS (cycle detection / topological sort / connected components).