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)
|