Depth First Search (DFS) is a generalization of the preorder traversal. Starting at some arbitrarily chosen vertex v, we mark v so that we
know we've visited it, process v, and then recursively traverse all unmarked vertices adjacent to v (v will be a different vertex with every new
method call). When we visit a vertex in which all of its neighbors have been visited, we return to its calling vertex, and visit one of its
unvisited neighbors, repeating the recursion in the same manner. We continue until we have visited all of the starting vertex's neighbors,
which means that we're done. The recursion (stack) guides us through the graph.
No comments:
Post a Comment