ALGORITHM TO TRAVERSE A TREE DEPTH FIRST.txt

ALGORITHM TO TRAVERSE A TREE DEPTH FIRST

To perform a depth-first search a tree is traversed as deep as possible from neighbour to neighbour before backtracking. What determines how deep is possible is that edges are followed, and no vertex is visited twice.  Vertices that have been visited are noted and kept track of. Visited nodes are tracked can be tracked in a boolean array and a stack to push nodes onto that are meant to be visited.


DFS(G,v)   ( v is the vertex where the search starts )
         Stack S := {};   ( start with an empty stack )
         for each vertex u, set visited[u] := false;
         push S, v;
         while (S is not empty) do
            u := pop S;
            if (not visited[u]) then
               visited[u] := true;
               for each unvisited neighbour w of u
                  push S, w;
            end if
         end while
      END DFS()