[prev] 62 [next]

Depth-first Traversal

Basic approach to depth-first traversal:
  • visit and mark current vertex
  • for each neighbour, traverse it recursively
    (choice in order to consider neighbours; we choose smallest first)
Notes:
  • we number ("mark") vertices as we visit them
    (so that we can later trace path through graph)
  • order ... counter; how many vertices traversed so far
  • visited[v] ... order in which vertex v was visited
In this context, traversal is also called search   (hence DFS)