Section 28.7 Check Point Questions5 questions

28.7.1

What is depth-first search?

28.7.2

Draw a DFS tree for the graph in Figure 28.3b starting from node A.

28.7.3

Draw a DFS tree for the graph in Figure 28.1 starting from vertex Atlanta.

28.7.4

What is the return type from invoking dfs(v)?

28.7.5

The depth-first search algorithm described in LiveExample 28.8 uses recursion. Alternatively, you can use a stack to implement it, as shown below. Point out the error in this algorithm and give a correct algorithm.

// Wrong version 
Tree dfs(vertex v) {
  push v into the stack;
  mark v visited;
 
  while (the stack is not empty) {
    pop a vertex, say u, from the stack
    visit u;
    for each neighbor w of u
      if (w has not been visited)
        push w into the stack; 
  }
}