In lecture we saw a variant of recursive depth-first search.
Recursive depth-first search is extremely simple and elegant if the
algorithm does not need to track additional information or return
any value:
dfs(G, src): // This function initializes the
isVisited = new dictionary // dictionary and calls the
for each vertex v in G: // recursive helper function.
isVisited[v] = false
recursiveDfs(G, src, isVisited)
recursiveDfs(G, src, isVisited): // This recursive function
isVisited[src] = true // searches the graph.
for each neighbor v of src:
if !isVisited[v]:
recursiveDfs(G, v, isVisited)
- Execute dfs on the following graph, using s as the source
vertex. Draw the stack frame diagram for the program as it
executes. (Assume that isVisited refers to a single copy of the
dictionary for all frames of the stack.)
- Modify the pseudocode above to accept a second vertex, dest, as
an argument. Return true if there is a path from src->dest in G,
and return false otherwise.
- Modify the pseudocode again to return the length of some
src->dest path (not necessarily the shortest path) if there is a
path from src to dest in G. If there is no src->dest path, return
-1.
- Write a version of breadth first search and depth first search
that determines if a graph is connected.
- Write a version of depth first search that returns all vertices
in the same component as some source vertex.